diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -175,6 +175,7 @@ algorithms/sort_heap.bench.cpp algorithms/stable_sort.bench.cpp libcxxabi/dynamic_cast.bench.cpp + libcxxabi/dynamic_cast_old_stress.bench.cpp allocation.bench.cpp deque.bench.cpp filesystem.bench.cpp diff --git a/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp b/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp --- a/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp +++ b/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp @@ -1,3 +1,11 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + #include #include "benchmark/benchmark.h" diff --git a/libcxx/benchmarks/libcxxabi/dynamic_cast_old_stress.bench.cpp b/libcxx/benchmarks/libcxxabi/dynamic_cast_old_stress.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/libcxxabi/dynamic_cast_old_stress.bench.cpp @@ -0,0 +1,88 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "benchmark/benchmark.h" + +template +struct C + : public virtual C, + public virtual C +{ + virtual ~C() {} +}; + +template +struct C +{ + virtual ~C() {} +}; + +template +struct B + : public virtual C, + public virtual C +{ +}; + +template +struct makeB; + +template +struct makeB, Depth> + : public B... +{ +}; + +template +struct A + : public makeB::type, Depth> +{ +}; + +constexpr std::size_t Width = 10; +constexpr std::size_t Depth = 5; + +template +void CastTo(benchmark::State& state) +{ + A a; + auto base = static_cast*>(&a); + + Destination *b = nullptr; + for (auto _ : state) { + b = dynamic_cast(base); + benchmark::DoNotOptimize(b); + } + + assert(b != 0); +} + +BENCHMARK(CastTo>); +BENCHMARK(CastTo>); + +BENCHMARK_MAIN(); + +/** + * Benchmark results: (release builds) + * + * libcxxabi: + * ---------------------------------------------------------------------- + * Benchmark Time CPU Iterations + * ---------------------------------------------------------------------- + * CastTo> 1997 ns 1997 ns 349247 + * CastTo> 256 ns 256 ns 2733871 + * + * libsupc++: + * ---------------------------------------------------------------------- + * Benchmark Time CPU Iterations + * ---------------------------------------------------------------------- + * CastTo> 5240 ns 5240 ns 133091 + * CastTo> 866 ns 866 ns 808600 + * + * + */ diff --git a/libcxxabi/src/private_typeinfo.cpp b/libcxxabi/src/private_typeinfo.cpp --- a/libcxxabi/src/private_typeinfo.cpp +++ b/libcxxabi/src/private_typeinfo.cpp @@ -75,6 +75,244 @@ namespace __cxxabiv1 { +namespace { + +struct derived_object_info { + const void* dynamic_ptr; + const __class_type_info* dynamic_type; + std::ptrdiff_t offset_to_derived; +}; + +/// A helper function that gets (dynamic_ptr, dynamic_type, offset_to_derived) from static_ptr. +void dyn_cast_get_derived_info(derived_object_info* info, const void* static_ptr) +{ +#if __has_feature(cxx_abi_relative_vtable) + // The vtable address will point to the first virtual function, which is 8 + // bytes after the start of the vtable (4 for the offset from top + 4 for + // the typeinfo component). + const int32_t* vtable = + *reinterpret_cast(static_ptr); + info->offset_to_derived = static_cast(vtable[-2]); + info->dynamic_ptr = static_cast(static_ptr) + info->offset_to_derived; + + // The typeinfo component is now a relative offset to a proxy. + int32_t offset_to_ti_proxy = vtable[-1]; + const uint8_t* ptr_to_ti_proxy = + reinterpret_cast(vtable) + offset_to_ti_proxy; + info->dynamic_type = *(reinterpret_cast(ptr_to_ti_proxy)); +#else + void **vtable = *static_cast(static_ptr); + info->offset_to_derived = reinterpret_cast(vtable[-2]); + info->dynamic_ptr = static_cast(static_ptr) + info->offset_to_derived; + info->dynamic_type = static_cast(vtable[-1]); +#endif +} + +/// A helper function for __dynamic_cast that casts a base sub-object pointer +/// to the object's dynamic type. +/// +/// This function returns the casting result directly. No further processing +/// required. +/// +/// Specifically, this function can only be called if the following pre- +/// condition holds: +/// * The dynamic type of the object pointed to by `static_ptr` is exactly +/// the same as `dst_type`. + +const void* dyn_cast_to_derived(const void* static_ptr, + const void* dynamic_ptr, + const __class_type_info* static_type, + const __class_type_info* dst_type, + std::ptrdiff_t offset_to_derived, + std::ptrdiff_t src2dst_offset) +{ + // We're downcasting from src_type to the complete object's dynamic type. + // This is a really hot path that can be further optimized with the + // `src2dst_offset` hint. + // In such a case, dynamic_ptr already gives the casting result if the + // casting ever succeeds. All we have to do now is to check static_ptr + // points to a public base sub-object of dynamic_ptr. + + if (src2dst_offset >= 0) + { + // The static type is a unique public non-virtual base type of + // dst_type at offset `src2dst_offset` from the origin of dst. + // Note that there might be other non-public static_type bases. The + // hint only guarantees that the public base is non-virtual and + // unique. So we have to check whether static_ptr points to that + // unique public base sub-object. + if (offset_to_derived != -src2dst_offset) + return nullptr; + return dynamic_ptr; + } + + if (src2dst_offset == -2) + { + // static_type is not a public base of dst_type. + return nullptr; + } + + // If src2dst_offset == -3, then: + // src_type is a multiple public base type but never a virtual + // base type. We can't conclude that static_ptr points to those + // public base sub-objects because there might be other non- + // public static_type bases. The search is inevitable. + + // Fallback to the slow path to check that static_type is a public + // base type of dynamic_type. + // Using giant short cut. Add that information to info. + __dynamic_cast_info info = { + dst_type, + static_ptr, + static_type, + src2dst_offset, + 0, 0, 0, 0, 0, 0, 0, 0, + 1, // number_of_dst_type + false, false, false + }; + // Do the search + dst_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, false); +#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // The following if should always be false because we should + // definitely find (static_ptr, static_type), either on a public + // or private path + if (info.path_dst_ptr_to_static_ptr == unknown) + { + // We get here only if there is some kind of visibility problem + // in client code. + static_assert(std::atomic::is_always_lock_free, ""); + static std::atomic error_count(0); + size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); + if ((error_count_snapshot & (error_count_snapshot-1)) == 0) + syslog(LOG_ERR, "dynamic_cast error 1: Both of the following type_info's " + "should have public visibility. At least one of them is hidden. %s" + ", %s.\n", static_type->name(), dynamic_type->name()); + // Redo the search comparing type_info's using strcmp + info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; + info.number_of_dst_type = 1; + dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, true); + } +#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // Query the search. + if (info.path_dst_ptr_to_static_ptr != public_path) + return nullptr; + + return dynamic_ptr; +} + +/// A helper function for __dynamic_cast that tries to perform a downcast +/// before giving up and falling back to the slow path. + +const void* dyn_cast_try_downcast(const void* static_ptr, + const void* dynamic_ptr, + const __class_type_info* dst_type, + const __class_type_info* dynamic_type, + std::ptrdiff_t src2dst_offset) +{ + if (src2dst_offset < 0) + { + // We can only optimize the case if the static type is a unique public + // base of dst_type. Give up. + return nullptr; + } + + // Pretend there is a dst_type object that leads to static_ptr. Later we + // will check whether this imagined dst_type object exists. If it exists + // then it will be the casting result. + const void* dst_ptr_to_static = reinterpret_cast(static_ptr) - src2dst_offset; + + if (reinterpret_cast(dst_ptr_to_static) < reinterpret_cast(dynamic_ptr)) + { + // The imagined dst_type object does not exist. Bail-out quickly. + return nullptr; + } + + // Try to search a path from dynamic_type to dst_type. + __dynamic_cast_info dynamic_to_dst_info = { + dynamic_type, + dst_ptr_to_static, + dst_type, + src2dst_offset, + 0, 0, 0, 0, 0, 0, 0, 0, + 1, // number_of_dst_type + false, false, false + }; + dynamic_type->search_above_dst(&dynamic_to_dst_info, dynamic_ptr, dynamic_ptr, public_path, false); + if (dynamic_to_dst_info.path_dst_ptr_to_static_ptr != unknown) { + // We have found at least one path from dynamic_ptr to dst_ptr. The + // downcast can succeed. + return dst_ptr_to_static; + } + + return nullptr; +} + +const void* dyn_cast_slow(const void* static_ptr, + const void* dynamic_ptr, + const __class_type_info* static_type, + const __class_type_info* dst_type, + const __class_type_info* dynamic_type, + std::ptrdiff_t src2dst_offset) +{ + // Not using giant short cut. Do the search + + // Initialize info struct for this search. + __dynamic_cast_info info = { + dst_type, + static_ptr, + static_type, + src2dst_offset, + 0, 0, 0, 0, 0, 0, 0, 0, 0, false, false, false + }; + + dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, false); +#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // The following if should always be false because we should + // definitely find (static_ptr, static_type), either on a public + // or private path + if (info.path_dst_ptr_to_static_ptr == unknown && + info.path_dynamic_ptr_to_static_ptr == unknown) + { + static_assert(std::atomic::is_always_lock_free, ""); + static std::atomic error_count(0); + size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); + if ((error_count_snapshot & (error_count_snapshot-1)) == 0) + syslog(LOG_ERR, "dynamic_cast error 2: One or more of the following type_info's " + "has hidden visibility or is defined in more than one translation " + "unit. They should all have public visibility. " + "%s, %s, %s.\n", static_type->name(), dynamic_type->name(), + dst_type->name()); + // Redo the search comparing type_info's using strcmp + info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; + dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, true); + } +#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // Query the search. + switch (info.number_to_static_ptr) + { + case 0: + if (info.number_to_dst_ptr == 1 && + info.path_dynamic_ptr_to_static_ptr == public_path && + info.path_dynamic_ptr_to_dst_ptr == public_path) + return info.dst_ptr_not_leading_to_static_ptr; + break; + case 1: + if (info.path_dst_ptr_to_static_ptr == public_path || + ( + info.number_to_dst_ptr == 0 && + info.path_dynamic_ptr_to_static_ptr == public_path && + info.path_dynamic_ptr_to_dst_ptr == public_path + ) + ) + return info.dst_ptr_leading_to_static_ptr; + break; + } + + return nullptr; +} + +} // namespace + // __shim_type_info __shim_type_info::~__shim_type_info() @@ -623,174 +861,46 @@ __dynamic_cast(const void *static_ptr, const __class_type_info *static_type, const __class_type_info *dst_type, std::ptrdiff_t src2dst_offset) { - // Possible future optimization: Take advantage of src2dst_offset - // Get (dynamic_ptr, dynamic_type) from static_ptr -#if __has_feature(cxx_abi_relative_vtable) - // The vtable address will point to the first virtual function, which is 8 - // bytes after the start of the vtable (4 for the offset from top + 4 for the typeinfo component). - const int32_t* vtable = - *reinterpret_cast(static_ptr); - int32_t offset_to_derived = vtable[-2]; - const void* dynamic_ptr = static_cast(static_ptr) + offset_to_derived; - - // The typeinfo component is now a relative offset to a proxy. - int32_t offset_to_ti_proxy = vtable[-1]; - const uint8_t* ptr_to_ti_proxy = - reinterpret_cast(vtable) + offset_to_ti_proxy; - const __class_type_info* dynamic_type = - *(reinterpret_cast(ptr_to_ti_proxy)); -#else - void **vtable = *static_cast(static_ptr); - ptrdiff_t offset_to_derived = reinterpret_cast(vtable[-2]); - const void* dynamic_ptr = static_cast(static_ptr) + offset_to_derived; - const __class_type_info* dynamic_type = static_cast(vtable[-1]); -#endif + derived_object_info derived_info; + dyn_cast_get_derived_info(&derived_info, static_ptr); // Initialize answer to nullptr. This will be changed from the search // results if a non-null answer is found. Regardless, this is what will // be returned. const void* dst_ptr = 0; - // Initialize info struct for this search. - __dynamic_cast_info info = {dst_type, static_ptr, static_type, src2dst_offset, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,}; // Find out if we can use a giant short cut in the search - if (is_equal(dynamic_type, dst_type, false)) + if (is_equal(derived_info.dynamic_type, dst_type, false)) { - // We're downcasting from src_type to the complete object's dynamic - // type. This is a really hot path that can be further optimized - // with the `src2dst_offset` hint. - // In such a case, dynamic_ptr already gives the casting result if the - // casting ever succeeds. All we have to do now is to check - // static_ptr points to a public base sub-object of dynamic_ptr. - - if (src2dst_offset >= 0) - { - // The static type is a unique public non-virtual base type of - // dst_type at offset `src2dst_offset` from the origin of dst. - // Note that there might be other non-public static_type bases. The - // hint only guarantees that the public base is non-virtual and - // unique. So we have to check whether static_ptr points to that - // unique public base sub-object. - if (offset_to_derived == -src2dst_offset) - dst_ptr = dynamic_ptr; - } - else if (src2dst_offset == -2) - { - // static_type is not a public base of dst_type. - dst_ptr = nullptr; - } - else - { - // If src2dst_offset == -3, then: - // src_type is a multiple public base type but never a virtual - // base type. We can't conclude that static_ptr points to those - // public base sub-objects because there might be other non- - // public static_type bases. The search is inevitable. - - // Fallback to the slow path to check that static_type is a public - // base type of dynamic_type. - // Using giant short cut. Add that information to info. - info.number_of_dst_type = 1; - // Do the search - dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, false); -#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // The following if should always be false because we should - // definitely find (static_ptr, static_type), either on a public - // or private path - if (info.path_dst_ptr_to_static_ptr == unknown) - { - // We get here only if there is some kind of visibility problem - // in client code. - static_assert(std::atomic::is_always_lock_free, ""); - static std::atomic error_count(0); - size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); - if ((error_count_snapshot & (error_count_snapshot-1)) == 0) - syslog(LOG_ERR, "dynamic_cast error 1: Both of the following type_info's " - "should have public visibility. At least one of them is hidden. %s" - ", %s.\n", static_type->name(), dynamic_type->name()); - // Redo the search comparing type_info's using strcmp - info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; - info.number_of_dst_type = 1; - dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, true); - } -#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // Query the search. - if (info.path_dst_ptr_to_static_ptr == public_path) - dst_ptr = dynamic_ptr; - } + dst_ptr = dyn_cast_to_derived(static_ptr, + derived_info.dynamic_ptr, + static_type, + dst_type, + derived_info.offset_to_derived, + src2dst_offset); } else { - if (src2dst_offset >= 0) - { - // Optimize toward downcasting: dst_type has one unique public - // static_type bases. Let's first try to do a downcast before - // falling back to the slow path. The downcast succeeds if there - // is at least one path regardless of visibility from - // dynamic_type to dst_type. - const void* dst_ptr_to_static = reinterpret_cast(static_ptr) - src2dst_offset; - if (reinterpret_cast(dst_ptr_to_static) >= reinterpret_cast(dynamic_ptr)) - { - // Try to search a path from dynamic_type to dst_type. - __dynamic_cast_info dynamic_to_dst_info = {dynamic_type, dst_ptr_to_static, dst_type, src2dst_offset}; - dynamic_to_dst_info.number_of_dst_type = 1; - dynamic_type->search_above_dst(&dynamic_to_dst_info, dynamic_ptr, dynamic_ptr, public_path, false); - if (dynamic_to_dst_info.path_dst_ptr_to_static_ptr != unknown) { - // We have found at least one path from dynamic_ptr to - // dst_ptr. The downcast can succeed. - dst_ptr = dst_ptr_to_static; - } - } - } + // Optimize toward downcasting: let's first try to do a downcast before + // falling back to the slow path. + dst_ptr = dyn_cast_try_downcast(static_ptr, + derived_info.dynamic_ptr, + dst_type, + derived_info.dynamic_type, + src2dst_offset); if (!dst_ptr) { - // Not using giant short cut. Do the search - dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, false); -#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // The following if should always be false because we should - // definitely find (static_ptr, static_type), either on a public - // or private path - if (info.path_dst_ptr_to_static_ptr == unknown && - info.path_dynamic_ptr_to_static_ptr == unknown) - { - static_assert(std::atomic::is_always_lock_free, ""); - static std::atomic error_count(0); - size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); - if ((error_count_snapshot & (error_count_snapshot-1)) == 0) - syslog(LOG_ERR, "dynamic_cast error 2: One or more of the following type_info's " - "has hidden visibility or is defined in more than one translation " - "unit. They should all have public visibility. " - "%s, %s, %s.\n", static_type->name(), dynamic_type->name(), - dst_type->name()); - // Redo the search comparing type_info's using strcmp - info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; - dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, true); - } -#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // Query the search. - switch (info.number_to_static_ptr) - { - case 0: - if (info.number_to_dst_ptr == 1 && - info.path_dynamic_ptr_to_static_ptr == public_path && - info.path_dynamic_ptr_to_dst_ptr == public_path) - dst_ptr = info.dst_ptr_not_leading_to_static_ptr; - break; - case 1: - if (info.path_dst_ptr_to_static_ptr == public_path || - ( - info.number_to_dst_ptr == 0 && - info.path_dynamic_ptr_to_static_ptr == public_path && - info.path_dynamic_ptr_to_dst_ptr == public_path - ) - ) - dst_ptr = info.dst_ptr_leading_to_static_ptr; - break; - } + dst_ptr = dyn_cast_slow(static_ptr, + derived_info.dynamic_ptr, + static_type, + dst_type, + derived_info.dynamic_type, + src2dst_offset); } } + return const_cast(dst_ptr); } diff --git a/libcxxabi/test/dynamic_cast_stress.pass.cpp b/libcxxabi/test/dynamic_cast_stress.pass.cpp deleted file mode 100644 --- a/libcxxabi/test/dynamic_cast_stress.pass.cpp +++ /dev/null @@ -1,82 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -// UNSUPPORTED: c++03 - -#include -#include -#include "support/timer.h" - -template -struct C - : public virtual C, - public virtual C -{ - virtual ~C() {} -}; - -template -struct C -{ - virtual ~C() {} -}; - -template -struct B - : public virtual C, - public virtual C -{ -}; - -template -struct makeB; - -template -struct makeB, Depth> - : public B... -{ -}; - -template -struct A - : public makeB::type, Depth> -{ -}; - -void test() -{ - const std::size_t Width = 10; - const std::size_t Depth = 5; - A a; - typedef B Destination; -// typedef A Destination; - Destination *b = nullptr; - { - timer t; - b = dynamic_cast((C*)&a); - } - assert(b != 0); -} - -int main(int, char**) -{ - test(); - - return 0; -} - -/* -Timing results I'm seeing (median of 3 microseconds): - - libc++abi gcc's dynamic_cast -B -O3 48.334 93.190 libc++abi 93% faster -B -Os 58.535 94.103 libc++abi 61% faster -A -O3 11.515 33.134 libc++abi 188% faster -A -Os 12.631 31.553 libc++abi 150% faster - -*/