blob: b1dac5a524e8b84465ae9c980ccfa59258cbb7c2 [file] [log] [blame] [edit]
// 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/compiler/assembler/assembler.h"
#include "vm/compiler/backend/il.h"
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 a whitelisted set of types,
// otherwise it will return a default stub which tail-calls
// subtypingtest/runtime code.
static RawInstructions* 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.
RawInstructions* OptimizedCodeForType(const AbstractType& type);
private:
#if !defined(TARGET_ARCH_DBC) && !defined(TARGET_ARCH_IA32)
#if !defined(DART_PRECOMPILED_RUNTIME)
RawInstructions* BuildCodeForType(const Type& type);
static void BuildOptimizedTypeTestStub(Assembler* assembler,
HierarchyInfo* hi,
const Type& type,
const Class& type_class);
static void BuildOptimizedTypeTestStubFastCases(Assembler* assembler,
HierarchyInfo* hi,
const Type& type,
const Class& type_class,
Register instance_reg,
Register class_id_reg);
static void BuildOptimizedSubtypeRangeCheck(Assembler* assembler,
const CidRangeVector& ranges,
Register class_id_reg,
Register instance_reg,
bool smi_is_ok);
static void BuildOptimizedSubclassRangeCheckWithTypeArguments(
Assembler* assembler,
HierarchyInfo* hi,
const Class& type_class,
const TypeArguments& type_parameters,
const TypeArguments& type_arguments);
static void BuildOptimizedSubclassRangeCheckWithTypeArguments(
Assembler* assembler,
HierarchyInfo* hi,
const Class& type_class,
const TypeArguments& type_parameters,
const TypeArguments& type_arguments,
const Register class_id_reg,
const Register instance_reg,
const Register instance_type_args_reg);
static void BuildOptimizedSubclassRangeCheck(Assembler* assembler,
const CidRangeVector& ranges,
Register class_id_reg,
Register instance_reg,
Label* check_failed);
static void BuildOptimizedTypeArgumentValueCheck(
Assembler* assembler,
HierarchyInfo* hi,
const AbstractType& type_arg,
intptr_t type_param_value_offset_i,
Label* check_failed);
static void BuildOptimizedTypeArgumentValueCheck(
Assembler* assembler,
HierarchyInfo* hi,
const AbstractType& type_arg,
intptr_t type_param_value_offset_i,
const Register class_id_reg,
const Register instance_type_args_reg,
const Register instantiator_type_args_reg,
const Register function_type_args_reg,
const Register type_arg_reg,
Label* check_failed);
#endif // !defined(DART_PRECOMPILED_RUNTIME)
#endif // !defined(TARGET_ARCH_DBC) && !defined(TARGET_ARCH_IA32)
TypeTestingStubNamer namer_;
ObjectStore* object_store_;
GrowableObjectArray& array_;
Instructions& instr_;
};
// It is assumed that the caller ensures, while this object lives there is no
// other access to [Isolate::Current()->object_store()->type_testing_stubs()].
class TypeTestingStubFinder {
public:
TypeTestingStubFinder();
// When serializing an AOT snapshot via our clustered snapshot writer, we
// write out references to the [Instructions] object for all the
// [AbstractType] objects we encounter.
//
// This method is used for this mapping of stub entrypoint addresses to the
// corresponding [Instructions] object.
RawInstructions* LookupByAddresss(uword entry_point) const;
// When generating an AOT snapshot as an assembly file (i.e. ".S" file) we
// need to generate labels for the type testing stubs.
//
// This method maps stub entrypoint addresses to meaningful names.
const char* StubNameFromAddresss(uword entry_point) const;
private:
// Sorts the tuples in [array_] according to entrypoint.
void SortTableForFastLookup();
// Returns the tuple index where [entry_point] was found.
intptr_t LookupInSortedArray(uword entry_point) const;
TypeTestingStubNamer namer_;
GrowableObjectArray& array_;
AbstractType& type_;
Code& code_;
Instructions& instr_;
};
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;
} else if (type.IsBoundedType()) {
// No support for bounded types.
return false;
}
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) {}
RawTypeArguments* 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);
RawAbstractType* 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 StackResource {
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_;
};
void RegisterTypeArgumentsUse(const Function& function,
TypeUsageInfo* type_usage_info,
const Class& klass,
Definition* type_arguments);
#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_