blob: b602c6acd087a83f95b8a1179413a3a0153cdecc [file] [log] [blame]
// Copyright (c) 2018, 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.
#ifndef RUNTIME_VM_TYPE_TESTING_STUBS_H_
#define RUNTIME_VM_TYPE_TESTING_STUBS_H_
#include "vm/object.h"
#if !defined(DART_PRECOMPILED_RUNTIME)
#include "vm/compiler/assembler/assembler.h"
#include "vm/compiler/backend/il.h"
#include "vm/compiler/stub_code_compiler.h"
#endif // !defined(DART_PRECOMPILED_RUNTIME)
namespace dart {
class TypeTestingStubNamer {
public:
TypeTestingStubNamer();
// Simple helper for stringinfying a [type] and prefix it with the type
// testing
//
// (only during dart_boostrap).
const char* StubNameForType(const AbstractType& type) const;
private:
const char* StringifyType(const AbstractType& type) const;
static const char* AssemblerSafeName(char* cname);
Library& lib_;
Class& klass_;
AbstractType& type_;
TypeArguments& type_arguments_;
String& string_;
};
class TypeTestingStubGenerator {
public:
// During bootstrapping it will return `null` for |void| and |dynamic| types,
// otherwise it will return a default stub which tail-calls
// subtypingtest/runtime code.
static CodePtr DefaultCodeForType(const AbstractType& type,
bool lazy_specialize = true);
#if !defined(DART_PRECOMPILED_RUNTIME)
static void SpecializeStubFor(Thread* thread, const AbstractType& type);
#endif
TypeTestingStubGenerator();
// Creates new stub for [type] (and registers the tuple in object store
// array) or returns default stub.
CodePtr OptimizedCodeForType(const AbstractType& type);
private:
#if !defined(TARGET_ARCH_IA32)
#if !defined(DART_PRECOMPILED_RUNTIME)
CodePtr BuildCodeForType(const Type& type);
static void BuildOptimizedTypeTestStub(
compiler::Assembler* assembler,
compiler::UnresolvedPcRelativeCalls* unresolved_calls,
const Code& slow_type_test_stub,
HierarchyInfo* hi,
const Type& type,
const Class& type_class);
static void BuildOptimizedTypeTestStubFastCases(
compiler::Assembler* assembler,
HierarchyInfo* hi,
const Type& type,
const Class& type_class);
static void BuildOptimizedSubtypeRangeCheck(compiler::Assembler* assembler,
const CidRangeVector& ranges,
bool smi_is_ok);
static void BuildOptimizedSubclassRangeCheckWithTypeArguments(
compiler::Assembler* assembler,
HierarchyInfo* hi,
const Type& type,
const Class& type_class,
const TypeArguments& type_parameters,
const TypeArguments& type_arguments);
static void BuildOptimizedSubclassRangeCheckWithTypeArguments(
compiler::Assembler* assembler,
HierarchyInfo* hi,
const Type& type,
const Class& type_class,
const TypeArguments& type_parameters,
const TypeArguments& type_arguments,
const Register class_id_reg,
const Register instance_type_args_reg);
static void BuildOptimizedSubclassRangeCheck(compiler::Assembler* assembler,
const CidRangeVector& ranges,
compiler::Label* check_failed);
static void BuildOptimizedTypeArgumentValueCheck(
compiler::Assembler* assembler,
HierarchyInfo* hi,
const AbstractType& type_arg,
intptr_t type_param_value_offset_i,
compiler::Label* check_failed);
#endif // !defined(DART_PRECOMPILED_RUNTIME)
#endif // !defined(TARGET_ARCH_IA32)
TypeTestingStubNamer namer_;
ObjectStore* object_store_;
};
template <typename T>
class ReusableHandleStack {
public:
explicit ReusableHandleStack(Zone* zone) : zone_(zone), handles_count_(0) {}
private:
T* Obtain() {
T* handle;
if (handles_count_ < handles_.length()) {
handle = handles_[handles_count_];
} else {
handle = &T::ZoneHandle(zone_);
handles_.Add(handle);
}
handles_count_++;
return handle;
}
void Release(T* handle) {
handles_count_--;
ASSERT(handles_count_ >= 0);
ASSERT(handles_[handles_count_] == handle);
}
Zone* zone_;
intptr_t handles_count_;
MallocGrowableArray<T*> handles_;
template <typename U>
friend class ScopedHandle;
};
template <typename T>
class ScopedHandle {
public:
explicit ScopedHandle(ReusableHandleStack<T>* stack)
: stack_(stack), handle_(stack_->Obtain()) {}
~ScopedHandle() { stack_->Release(handle_); }
T& operator*() { return *handle_; }
T* operator->() { return handle_; }
private:
ReusableHandleStack<T>* stack_;
T* handle_;
};
// Attempts to find a [Class] from un-instantiated [TypeArgument] vector to
// which it's type parameters are referring to.
//
// If the given type argument vector contains references to type parameters,
// this finder will either return a valid class if all of the type parameters
// come from the same class and returns `null` otherwise.
//
// It is safe to use this class inside loops since the implementation uses a
// [ReusableHandleStack] (which in pratice will only use a handful of handles).
class TypeArgumentClassFinder {
public:
explicit TypeArgumentClassFinder(Zone* zone)
: klass_(Class::Handle(zone)),
type_(AbstractType::Handle(zone)),
type_arguments_handles_(zone) {}
const Class& FindClass(const TypeArguments& ta) {
klass_ = Class::null();
const intptr_t len = ta.Length();
for (intptr_t i = 0; i < len; ++i) {
type_ = ta.TypeAt(i);
if (!FindClassFromType(type_)) {
klass_ = Class::null();
break;
}
}
return klass_;
}
private:
bool FindClassFromType(const AbstractType& type) {
if (type.IsTypeParameter()) {
const TypeParameter& parameter = TypeParameter::Cast(type);
if (!parameter.IsClassTypeParameter()) {
return false;
}
if (klass_.IsNull()) {
klass_ = parameter.parameterized_class();
} else {
// Dart has no support for nested classes.
ASSERT(klass_.raw() == parameter.parameterized_class());
}
return true;
} else if (type.IsFunctionType()) {
// No support for function types yet.
return false;
} else if (type.IsTypeRef()) {
// No support for recursive types.
return false;
} else if (type.IsType()) {
ScopedHandle<TypeArguments> type_arguments(&type_arguments_handles_);
*type_arguments = Type::Cast(type).arguments();
const intptr_t len = type_arguments->Length();
for (intptr_t i = 0; i < len; ++i) {
type_ = type_arguments->TypeAt(i);
if (!FindClassFromType(type_)) {
return false;
}
}
return true;
}
UNREACHABLE();
return false;
}
Class& klass_;
AbstractType& type_;
ReusableHandleStack<TypeArguments> type_arguments_handles_;
};
// Used for instantiating a [TypeArguments] which contains references to type
// parameters based on an instantiator [TypeArguments] vector.
//
// It is safe to use this class inside loops since the implementation uses a
// [ReusableHandleStack] (which in pratice will only use a handful of handles).
class TypeArgumentInstantiator {
public:
explicit TypeArgumentInstantiator(Zone* zone)
: klass_(Class::Handle(zone)),
type_(AbstractType::Handle(zone)),
instantiator_type_arguments_(TypeArguments::Handle(zone)),
type_arguments_handles_(zone),
type_handles_(zone) {}
TypeArgumentsPtr Instantiate(
const Class& klass,
const TypeArguments& type_arguments,
const TypeArguments& instantiator_type_arguments) {
instantiator_type_arguments_ = instantiator_type_arguments.raw();
return InstantiateTypeArguments(klass, type_arguments).raw();
}
private:
const TypeArguments& InstantiateTypeArguments(
const Class& klass,
const TypeArguments& type_arguments);
AbstractTypePtr InstantiateType(const AbstractType& type);
Class& klass_;
AbstractType& type_;
TypeArguments& instantiator_type_arguments_;
ReusableHandleStack<TypeArguments> type_arguments_handles_;
ReusableHandleStack<Type> type_handles_;
};
// Collects data on how [Type] objects are used in generated code.
class TypeUsageInfo : public ThreadStackResource {
public:
explicit TypeUsageInfo(Thread* thread);
~TypeUsageInfo();
void UseTypeInAssertAssignable(const AbstractType& type);
void UseTypeArgumentsInInstanceCreation(const Class& klass,
const TypeArguments& ta);
// Finalize the collected type usage information.
void BuildTypeUsageInformation();
// Query if [type] is very likely used in a type test (can give
// false-positives and false-negatives, but tries to make a very good guess)
bool IsUsedInTypeTest(const AbstractType& type);
private:
template <typename T>
class ObjectSetTrait {
public:
// Typedefs needed for the DirectChainedHashMap template.
typedef const T* Key;
typedef const T* Value;
typedef const T* Pair;
static Key KeyOf(Pair kv) { return kv; }
static Value ValueOf(Pair kv) { return kv; }
static inline intptr_t Hashcode(Key key) { return key->Hash(); }
};
class TypeSetTrait : public ObjectSetTrait<const AbstractType> {
public:
static inline bool IsKeyEqual(const AbstractType* pair,
const AbstractType* key) {
return pair->Equals(*key);
}
};
class TypeArgumentsSetTrait : public ObjectSetTrait<const TypeArguments> {
public:
static inline bool IsKeyEqual(const TypeArguments* pair,
const TypeArguments* key) {
return pair->raw() == key->raw();
}
};
class TypeParameterSetTrait : public ObjectSetTrait<const TypeParameter> {
public:
static inline bool IsKeyEqual(const TypeParameter* pair,
const TypeParameter* key) {
return pair->raw() == key->raw();
}
};
typedef DirectChainedHashMap<TypeSetTrait> TypeSet;
typedef DirectChainedHashMap<TypeArgumentsSetTrait> TypeArgumentsSet;
typedef DirectChainedHashMap<TypeParameterSetTrait> TypeParameterSet;
// Runs an (early terminated) fix-point algorithm which propagates type
// arguments. For example:
//
// class Base<X> {}
//
// class Foo<A, B> extends Base<B> {
// foo() => new Map<List<B>, A>();
// }
//
// main() {
// new Foo<String, int>();
// new Map<double, bool>();
// }
//
// will end up adding new type argument vectors to the per-class instantiator
// type argument vector set:
//
// Foo:
// <int, String, int>
// Map:
// <List<int>, String>
// <double, bool>
//
void PropagateTypeArguments(ClassTable* class_table, intptr_t cid_count);
// Collects all type parameters we are doing assert assignable checks against.
void CollectTypeParametersUsedInAssertAssignable(TypeParameterSet* set);
// All types which flow into any of the type parameters in [set] will be added
// to the set of types we test against.
void UpdateAssertAssignableTypes(ClassTable* class_table,
intptr_t cid_count,
TypeParameterSet* set);
void AddToSetIfParameter(TypeParameterSet* set,
const AbstractType* type,
TypeParameter* param);
void AddTypeToSet(TypeSet* set, const AbstractType* type);
Zone* zone_;
TypeArgumentClassFinder finder_;
TypeSet assert_assignable_types_;
TypeArgumentsSet* instance_creation_arguments_;
Class& klass_;
};
#if !defined(DART_PRECOMPILED_RUNTIME)
void RegisterTypeArgumentsUse(const Function& function,
TypeUsageInfo* type_usage_info,
const Class& klass,
Definition* type_arguments);
#endif
#if !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
void DeoptimizeTypeTestingStubs();
#endif // !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
} // namespace dart
#endif // RUNTIME_VM_TYPE_TESTING_STUBS_H_