[libc++abi] Refactor around __dynamic_cast

This commit contains refactorings around __dynamic_cast without changing
its behavior. 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.

Differential Revision: https://reviews.llvm.org/D138006

2 files changed, 271 insertions, 233 deletions

diff --git a/libcxxabi/src/private_typeinfo.cpp b/libcxxabi/src/private_typeinfo.cpp
index c737d96..82db4bb 100644
--- a/libcxxabi/src/private_typeinfo.cpp
+++ b/libcxxabi/src/private_typeinfo.cpp
@@ -75,6 +75,254 @@ static inline ptrdiff_t update_offset_to_base(const char* vtable,
 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()
@@ -623,174 +871,46 @@ 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))
+    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<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;
-        }
+        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<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;
-                }
-            }
-        }
+        // 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);
 }
 
diff --git a/libcxxabi/test/dynamic_cast_stress.pass.cpp b/libcxxabi/test/dynamic_cast_stress.pass.cpp
deleted file mode 100644
index 19dba5f..0000000
--- 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 <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
-
-*/