[libc++abi] Improve performance of __dynamic_cast

[Lancern]

Summary

The original __dynamic_cast implementation does not use the ABI-provided src2dst_offset parameter which helps improve performance on the hot paths. This patch improves the performance on the hot paths in __dynamic_cast by leveraging hints provided by the src2dst_offset parameter. This patch also includes a performance benchmark suite for the __dynamic_cast implementation.

[philnik]

Could you provide before and after numbers for the benchmark?

[Lancern]

In D137315#3904800, @philnik wrote:

Could you provide before and after numbers for the benchmark?

The following text file contains the benchmark results. The numbers are measured in nanoseconds.

benchmark-results.txt5 KBDownload

[philnik]

In D137315#3904913, @Lancern wrote:

In D137315#3904800, @philnik wrote:

Could you provide before and after numbers for the benchmark?

The following text file contains the benchmark results. The numbers are measured in nanoseconds.

benchmark-results.txt5 KBDownload

These numbers look really good! From what I can tell the changes are correct, but someone else should take a look to make sure I didn't miss anything. I'm not super familiar with libc++abi.

libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp

1

Please add the license comment.

libcxxabi/src/private_typeinfo.cpp

863–864

Please remove this comment.

875–876

Please make sure there is sufficient test coverage for the cases you are special-casing for here and if not add tests. The tests are located in libcxxabi/test. I also noticed that there is dynamic_cast_stress.pass.cpp in there. Could you maybe refactor it to a benchmark and provide numbers for that?

878

Could you maybe factor the code into a few helper functions? Putting the helpers into an anonymous namespace should result in the same code gen.

[Lancern]

Resolve the reviewed issues posted at D137315#3910662

[Lancern]

I instrumented private_typeinfo.cpp with gcov and get its coverage during unit tests. The coverage shows that all new branches introduced in this patch series are covered by existing unit tests.

Below is the gcov report for private_typeinfo.cpp if you're interested.

private_typeinfo.cpp.gcov85 KBDownload

[Lancern]

Ping

[EricWF]

Do you know why the hint wasn't initially used? Was there a point where compilers didn't actually provide the hints?

Also, do you think there would be a way to split this change into two? One that does the refactoring without changing behavior, and another (hopefully much smaller) change that starts taking advantage of the src2dst_offset hint?

I think it would be much easier to understand the changes here if they were separated from the nice cleanup that was done here.

libcxxabi/src/private_typeinfo.cpp

260

Would it be better to pass this struct in rather than taking a bunch of very similar parameters with the same type as function arguments?

It seems like that would be less bug prone.

866

Seems like it would be a better API to have dyn_cast_get_derived_info to return the info struct rather than taking it as an input parameter.

[Lancern]

In D137315#3925193, @EricWF wrote:

Do you know why the hint wasn't initially used? Was there a point where compilers didn't actually provide the hints?

I tested some compilers supported by Compiler Explorer and:

• For GCC, the oldest version (4.1.2) supported by Compiler Explorer provides the hints;
• Clang starts providing the hints since version 3.3;
• ICC starts providing the hints since version 19.0.0;
• For ICX, the oldest version (2021.1.2) supported by Compiler Explorer provides the hints.

MSVC is not tested since it does not generate code compatible with the Itanium ABI.

In D137315#3925193, @EricWF wrote:

Also, do you think there would be a way to split this change into two? One that does the refactoring without changing behavior, and another (hopefully much smaller) change that starts taking advantage of the src2dst_offset hint?

Actually this revision contains two commits. The first commit starts taking advantage of the src2dst_offset hint, and the second commit refactors without changing behavior. Looks like Differential only shows the latest commit in the patch series.

[Lancern]

This revision is abandoned since I screwed it with multiple commits. I re-created 2 new revisions for each of the 2 commits contained in this revision, respectively:

• D138005 that contains the behavior-changing commit that takes uses of the src2dst_offset hint;
• D138006 that contains the refactorings without changing behaviors.

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
     filesystem.bench.cpp
     format_to_n.bench.cpp
     format_to.bench.cpp
     format.bench.cpp
     formatted_size.bench.cpp
     formatter_float.bench.cpp

libcxx/benchmarks/libcxxabi/dynamic_cast.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 <cstddef>
 
 #include "benchmark/benchmark.h"
 
 template <std::size_t Depth>
 struct Chain : Chain<Depth - 1> {};
 
 template <>

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 "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::__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>
+{
+};
+
+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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 #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(), 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<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};
+        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
-
-*/