[libc++abi] Refactoring works around __dynamic_cast

[ldionne]

Summary

This commit contains refactorings around __dynamic_cast without changing its
behaviors. Some important changes include:

• Refactor __dynamic_cast into various small helper functions;
• Move dynamic_cast_stress.pass.cpp to libcxx/benchmarks and refactor it into a benchmark. The benchmark performance numbers are updated as well.

[tschuett]

libcxxabi/src/private_typeinfo.cpp

155

If you make the if explicit, you get too much indentation?

[Lancern]

Rebase onto the main branch so that CI triggers correctly

[avogelsgesang]

Hi @Lancern,

Thanks for looking into the performance of dynamic_cast and for splitting your initial patch from https://reviews.llvm.org/D137315!
Unfortunately, it looks like your patch is still not rebased onto current main. E.g., your patch claims to delete a couple of lines which are not currently on https://github.com/llvm/llvm-project/blob/main/libcxxabi/src/private_typeinfo.cpp. I marked one of those examples below. That's also why the CI currently fails (see "patch application failed" link further up on this page). Let's get that sorted out first, and as soon as the diff is correct, I will start reviewing your changes (I see little value in reviewing a non-applicable patch)

libcxxabi/src/private_typeinfo.cpp

667

E.g., here: this line of code is not currently in https://github.com/llvm/llvm-project/blob/main/libcxxabi/src/private_typeinfo.cpp but your patch still tries to delete it.

[avogelsgesang]

Ah, now I understand how you are planning to apply your changes. I assumed you first wanted to apply this patch, and then https://reviews.llvm.org/D138005 on top of it (i.e. first the refactoring, then the perf improvement). But you want to apply them exactly the other way around.

In that case, you need to set the "parent revision" here on phabricator, such that the CI knows how to apply your patch...

[Lancern]

Seems like the failed unit tests are not related to this patch nor the parent revision.

[philnik]

In D138006#3986040, @Lancern wrote:

Seems like the failed unit tests are not related to this patch nor the parent revision.

The failures on apple look related. The ones on AIX are probably just timeouts.

[avogelsgesang]

Here is one of the error messages produced on Apple

/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/w4-4macminivaultcom-local/llvm-project/libcxx-ci/libcxxabi/src/private_typeinfo.cpp:189:53: error: use of undeclared identifier 'dynamic_type'
                    ", %s.\n", static_type->name(), dynamic_type->name());
                                                    ^
/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/w4-4macminivaultcom-local/llvm-project/libcxx-ci/libcxxabi/src/private_typeinfo.cpp:191:69: warning: missing field 'dst_ptr_not_leading_to_static_ptr' initializer [-Wmissing-field-initializers]
        info = {dst_type, static_ptr, static_type, src2dst_offset, 0};
                                                                    ^
/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/w4-4macminivaultcom-local/llvm-project/libcxx-ci/libcxxabi/src/private_typeinfo.cpp:193:9: error: use of undeclared identifier 'dynamic_type'
        dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, true);
        ^
/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/w4-4macminivaultcom-local/llvm-project/libcxx-ci/libcxxabi/src/private_typeinfo.cpp:286:69: warning: missing field 'dst_ptr_not_leading_to_static_ptr' initializer [-Wmissing-field-initializers]
        info = {dst_type, static_ptr, static_type, src2dst_offset, 0};
                                                                    ^
2 warnings and 2 errors generated.

It seems your code inside the _LIBCXXABI_FORGIVING_DYNAMIC_CAST ifdef is incorrect. This flag is apparently only enabled on Apple

[avogelsgesang]

Seems like the failed unit tests are not related to this patch nor the parent revision.

I restarted the test run for the parent revision, and the parent revision now indeed has a green CI run

[Lancern]

Fix build issues on Apple system

[Lancern]

Rebase onto b945bb246ad9.

[Lancern]

Rebase work onto the latest main.

[Lancern]

Sync with the parent commit.

[philnik]

Thanks! LGTM.

[ldionne]

[Github PR transition cleanup]

Commandeering to rebase and update.

[ldionne]

Rebase and a few minor NFC tweaks.

libcxx/benchmarks/CMakeLists.txt

set(BENCHMARK_TESTS
     algorithms/ranges_push_heap.bench.cpp
     algorithms/ranges_sort.bench.cpp
     algorithms/ranges_sort_heap.bench.cpp
     algorithms/ranges_stable_sort.bench.cpp
     algorithms/sort.bench.cpp
     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
     deque_iterator.bench.cpp
     filesystem.bench.cpp
     format_to_n.bench.cpp
     format_to.bench.cpp
     format.bench.cpp
     formatted_size.bench.cpp

libcxx/benchmarks/libcxxabi/dynamic_cast_old_stress.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <cassert>
+#include <cstddef>
+#include <utility>
+
+#include "benchmark/benchmark.h"
+
+template <std::size_t Indx, std::size_t Depth>
+struct C : public virtual C<Indx, Depth - 1>, public virtual C<Indx + 1, Depth - 1> {
+  virtual ~C() {}
+};
+
+template <std::size_t Indx>
+struct C<Indx, 0> {
+  virtual ~C() {}
+};
+
+template <std::size_t Indx, std::size_t Depth>
+struct B : public virtual C<Indx, Depth - 1>, public virtual C<Indx + 1, Depth - 1> {};
+
+template <class Indx, std::size_t Depth>
+struct makeB;
+
+template <std::size_t... Indx, std::size_t Depth>
+struct makeB<std::index_sequence<Indx...>, Depth> : public B<Indx, Depth>... {};
+
+template <std::size_t Width, std::size_t Depth>
+struct A : public makeB<std::make_index_sequence<Width>, Depth> {};
+
+constexpr std::size_t Width = 10;
+constexpr std::size_t Depth = 5;
+
+template <typename Destination>
+void CastTo(benchmark::State& state) {
+  A<Width, Depth> a;
+  auto base = static_cast<C<Width / 2, 0>*>(&a);
+
+  Destination* b = nullptr;
+  for (auto _ : state) {
+    b = dynamic_cast<Destination*>(base);
+    benchmark::DoNotOptimize(b);
+  }
+
+  assert(b != 0);
+}
+
+BENCHMARK(CastTo<B<Width / 2, Depth>>);
+BENCHMARK(CastTo<A<Width, Depth>>);
+
+BENCHMARK_MAIN();
+
+/**
+ * Benchmark results: (release builds)
+ *
+ * libcxxabi:
+ * ----------------------------------------------------------------------
+ * Benchmark                            Time             CPU   Iterations
+ * ----------------------------------------------------------------------
+ * CastTo<B<Width / 2, Depth>>       1997 ns         1997 ns       349247
+ * CastTo<A<Width, Depth>>            256 ns          256 ns      2733871
+ *
+ * libsupc++:
+ * ----------------------------------------------------------------------
+ * Benchmark                            Time             CPU   Iterations
+ * ----------------------------------------------------------------------
+ * CastTo<B<Width / 2, Depth>>       5240 ns         5240 ns       133091
+ * CastTo<A<Width, Depth>>            866 ns          866 ns       808600
+ *
+ *
+ */

libcxxabi/src/private_typeinfo.cpp

 #else
   return *reinterpret_cast<const ptrdiff_t*>(vtable + offset_to_base);
 #endif
 }
 
 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<const int32_t* const*>(static_ptr);
+    info->offset_to_derived = static_cast<std::ptrdiff_t>(vtable[-2]);
+    info->dynamic_ptr = static_cast<const char*>(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<const uint8_t*>(vtable) + offset_to_ti_proxy;
+    info->dynamic_type = *(reinterpret_cast<const __class_type_info* const*>(ptr_to_ti_proxy));
+#else
+    void **vtable = *static_cast<void ** const *>(static_ptr);
+    info->offset_to_derived = reinterpret_cast<ptrdiff_t>(vtable[-2]);
+    info->dynamic_ptr = static_cast<const char*>(static_ptr) + info->offset_to_derived;
+    info->dynamic_type = static_cast<const __class_type_info*>(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<size_t>::is_always_lock_free, "");
+        static std::atomic<size_t> 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(), dst_type->name());
+        // Redo the search comparing type_info's using strcmp
+        info = {
+            dst_type,
+            static_ptr,
+            static_type,
+            src2dst_offset,
+            0, 0, 0, 0, 0, 0, 0, 0, 0, false, false, false
+        };
+        info.number_of_dst_type = 1;
+        dst_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<const char*>(static_ptr) - src2dst_offset;
+
+    if (reinterpret_cast<std::intptr_t>(dst_ptr_to_static) < reinterpret_cast<std::intptr_t>(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<size_t>::is_always_lock_free, "");
+        static std::atomic<size_t> 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, 0, 0, 0, 0, 0, 0, 0, 0, false, false, false
+        };
+        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()
 {
 }
 
 void __shim_type_info::noop1() const {}
 void __shim_type_info::noop2() const {}

 // If there is a public path from (dynamic_ptr, dynamic_type) to
 //    (static_ptr, static_type), then return dynamic_ptr.
 // Else return nullptr.
 
 extern "C" _LIBCXXABI_FUNC_VIS void *
 __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<const int32_t* const*>(static_ptr);
-    int32_t offset_to_derived = vtable[-2];
-    const void* dynamic_ptr = static_cast<const char*>(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<const uint8_t*>(vtable) + offset_to_ti_proxy;
-    const __class_type_info* dynamic_type =
-        *(reinterpret_cast<const __class_type_info* const*>(ptr_to_ti_proxy));
-#else
-    void **vtable = *static_cast<void ** const *>(static_ptr);
-    ptrdiff_t offset_to_derived = reinterpret_cast<ptrdiff_t>(vtable[-2]);
-    const void* dynamic_ptr = static_cast<const char*>(static_ptr) + offset_to_derived;
-    const __class_type_info* dynamic_type = static_cast<const __class_type_info*>(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))
-    {
-        // 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<size_t>::is_always_lock_free, "");
-                static std::atomic<size_t> 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;
-        }
-    }
-    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<const char*>(static_ptr) - src2dst_offset;
-            if (reinterpret_cast<std::intptr_t>(dst_ptr_to_static) >= reinterpret_cast<std::intptr_t>(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;
-                }
-            }
-        }
+    if (is_equal(derived_info.dynamic_type, dst_type, false))
+        dst_ptr = dyn_cast_to_derived(static_ptr,
+                                      derived_info.dynamic_ptr,
+                                      static_type,
+                                      dst_type,
+                                      derived_info.offset_to_derived,
+                                      src2dst_offset);
+        // 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<size_t>::is_always_lock_free, "");
-                static std::atomic<size_t> 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<void*>(dst_ptr);
 }
 
 #ifdef __clang__
 #pragma clang diagnostic pop
 #endif
 
 // Call this function when you hit a static_type which is a base (above) a dst_type.

libcxxabi/test/dynamic_cast_stress.pass.cpp

-//===----------------------------------------------------------------------===//
-//
-// 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 <cassert>
-#include <tuple>
-#include "support/timer.h"
-
-template <std::size_t Indx, std::size_t Depth>
-struct C
-    : public virtual C<Indx, Depth-1>,
-      public virtual C<Indx+1, Depth-1>
-{
-    virtual ~C() {}
-};
-
-template <std::size_t Indx>
-struct C<Indx, 0>
-{
-    virtual ~C() {}
-};
-
-template <std::size_t Indx, std::size_t Depth>
-struct B
-    : public virtual C<Indx, Depth-1>,
-      public virtual C<Indx+1, Depth-1>
-{
-};
-
-template <class Indx, std::size_t Depth>
-struct makeB;
-
-template <std::size_t ...Indx, std::size_t Depth>
-struct makeB<std::__tuple_indices<Indx...>, Depth>
-    : public B<Indx, Depth>...
-{
-};
-
-template <std::size_t Width, std::size_t Depth>
-struct A
-    : public makeB<typename std::__make_tuple_indices<Width>::type, Depth>
-{
-};
-
-void test()
-{
-    const std::size_t Width = 10;
-    const std::size_t Depth = 5;
-    A<Width, Depth> a;
-    typedef B<Width/2, Depth> Destination;
-//    typedef A<Width, Depth> Destination;
-    Destination *b = nullptr;
-    {
-        timer t;
-        b = dynamic_cast<Destination*>((C<Width/2, 0>*)&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<Width/2, Depth> -O3      48.334         93.190           libc++abi 93% faster
-B<Width/2, Depth> -Os      58.535         94.103           libc++abi 61% faster
-A<Width, Depth>   -O3      11.515         33.134           libc++abi 188% faster
-A<Width, Depth>   -Os      12.631         31.553           libc++abi 150% faster
-
-*/