diff --git a/libcxx/include/__config b/libcxx/include/__config index 5f62b974170f..c97cbae96fba 100644 --- a/libcxx/include/__config +++ b/libcxx/include/__config @@ -1,1231 +1,1231 @@ // -*- C++ -*- //===----------------------------------------------------------------------===// // // 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 // //===----------------------------------------------------------------------===// #ifndef _LIBCPP___CONFIG #define _LIBCPP___CONFIG #include <__config_site> #if defined(_MSC_VER) && !defined(__clang__) # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # define _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER # endif #endif #ifndef _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER # pragma GCC system_header #endif #if defined(__apple_build_version__) # define _LIBCPP_COMPILER_CLANG_BASED # define _LIBCPP_APPLE_CLANG_VER (__apple_build_version__ / 10000) #elif defined(__clang__) # define _LIBCPP_COMPILER_CLANG_BASED # define _LIBCPP_CLANG_VER (__clang_major__ * 100 + __clang_minor__) #elif defined(__GNUC__) # define _LIBCPP_COMPILER_GCC #elif defined(_MSC_VER) # define _LIBCPP_COMPILER_MSVC #endif #ifdef __cplusplus -# define _LIBCPP_VERSION 15006 +# define _LIBCPP_VERSION 15007 # define _LIBCPP_CONCAT_IMPL(_X, _Y) _X##_Y # define _LIBCPP_CONCAT(_X, _Y) _LIBCPP_CONCAT_IMPL(_X, _Y) // Valid C++ identifier that revs with every libc++ version. This can be used to // generate identifiers that must be unique for every released libc++ version. # define _LIBCPP_VERSIONED_IDENTIFIER _LIBCPP_CONCAT(v, _LIBCPP_VERSION) # if __STDC_HOSTED__ == 0 # define _LIBCPP_FREESTANDING # endif # ifndef _LIBCPP_STD_VER # if __cplusplus <= 201103L # define _LIBCPP_STD_VER 11 # elif __cplusplus <= 201402L # define _LIBCPP_STD_VER 14 # elif __cplusplus <= 201703L # define _LIBCPP_STD_VER 17 # elif __cplusplus <= 202002L # define _LIBCPP_STD_VER 20 # else # define _LIBCPP_STD_VER 22 // current year, or date of c++2b ratification # endif # endif // _LIBCPP_STD_VER # if defined(__ELF__) # define _LIBCPP_OBJECT_FORMAT_ELF 1 # elif defined(__MACH__) # define _LIBCPP_OBJECT_FORMAT_MACHO 1 # elif defined(_WIN32) # define _LIBCPP_OBJECT_FORMAT_COFF 1 # elif defined(__wasm__) # define _LIBCPP_OBJECT_FORMAT_WASM 1 # elif defined(_AIX) # define _LIBCPP_OBJECT_FORMAT_XCOFF 1 # else // ... add new file formats here ... # endif # if _LIBCPP_ABI_VERSION >= 2 // Change short string representation so that string data starts at offset 0, // improving its alignment in some cases. # define _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT // Fix deque iterator type in order to support incomplete types. # define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE // Fix undefined behavior in how std::list stores its linked nodes. # define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB // Fix undefined behavior in how __tree stores its end and parent nodes. # define _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB // Fix undefined behavior in how __hash_table stores its pointer types. # define _LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB # define _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB # define _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE // Define a key function for `bad_function_call` in the library, to centralize // its vtable and typeinfo to libc++ rather than having all other libraries // using that class define their own copies. # define _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION // Override the default return value of exception::what() for // bad_function_call::what() with a string that is specific to // bad_function_call (see http://wg21.link/LWG2233). This is an ABI break // because it changes the vtable layout of bad_function_call. # define _LIBCPP_ABI_BAD_FUNCTION_CALL_GOOD_WHAT_MESSAGE // Enable optimized version of __do_get_(un)signed which avoids redundant copies. # define _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET // Give reverse_iterator one data member of type T, not two. // Also, in C++17 and later, don't derive iterator types from std::iterator. # define _LIBCPP_ABI_NO_ITERATOR_BASES // Use the smallest possible integer type to represent the index of the variant. // Previously libc++ used "unsigned int" exclusively. # define _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION // Unstable attempt to provide a more optimized std::function # define _LIBCPP_ABI_OPTIMIZED_FUNCTION // All the regex constants must be distinct and nonzero. # define _LIBCPP_ABI_REGEX_CONSTANTS_NONZERO // Re-worked external template instantiations for std::string with a focus on // performance and fast-path inlining. # define _LIBCPP_ABI_STRING_OPTIMIZED_EXTERNAL_INSTANTIATION // Enable clang::trivial_abi on std::unique_ptr. # define _LIBCPP_ABI_ENABLE_UNIQUE_PTR_TRIVIAL_ABI // Enable clang::trivial_abi on std::shared_ptr and std::weak_ptr # define _LIBCPP_ABI_ENABLE_SHARED_PTR_TRIVIAL_ABI // std::random_device holds some state when it uses an implementation that gets // entropy from a file (see _LIBCPP_USING_DEV_RANDOM). When switching from this // implementation to another one on a platform that has already shipped // std::random_device, one needs to retain the same object layout to remain ABI // compatible. This switch removes these workarounds for platforms that don't care // about ABI compatibility. # define _LIBCPP_ABI_NO_RANDOM_DEVICE_COMPATIBILITY_LAYOUT // Don't export the legacy __basic_string_common class and its methods from the built library. # define _LIBCPP_ABI_DO_NOT_EXPORT_BASIC_STRING_COMMON // Don't export the legacy __vector_base_common class and its methods from the built library. # define _LIBCPP_ABI_DO_NOT_EXPORT_VECTOR_BASE_COMMON // According to the Standard, `bitset::operator[] const` returns bool # define _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL // Remove the base 10 implementation of std::to_chars from the dylib. // The implementation moved to the header, but we still export the symbols from // the dylib for backwards compatibility. # define _LIBCPP_ABI_DO_NOT_EXPORT_TO_CHARS_BASE_10 # elif _LIBCPP_ABI_VERSION == 1 # if !(defined(_LIBCPP_OBJECT_FORMAT_COFF) || defined(_LIBCPP_OBJECT_FORMAT_XCOFF)) // Enable compiling copies of now inline methods into the dylib to support // applications compiled against older libraries. This is unnecessary with // COFF dllexport semantics, since dllexport forces a non-inline definition // of inline functions to be emitted anyway. Our own non-inline copy would // conflict with the dllexport-emitted copy, so we disable it. For XCOFF, // the linker will take issue with the symbols in the shared object if the // weak inline methods get visibility (such as from -fvisibility-inlines-hidden), // so disable it. # define _LIBCPP_DEPRECATED_ABI_LEGACY_LIBRARY_DEFINITIONS_FOR_INLINE_FUNCTIONS # endif // Feature macros for disabling pre ABI v1 features. All of these options // are deprecated. # if defined(__FreeBSD__) # define _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR # endif # endif # if defined(_LIBCPP_BUILDING_LIBRARY) || _LIBCPP_ABI_VERSION >= 2 // Enable additional explicit instantiations of iostreams components. This // reduces the number of weak definitions generated in programs that use // iostreams by providing a single strong definition in the shared library. # define _LIBCPP_ABI_ENABLE_ADDITIONAL_IOSTREAM_EXPLICIT_INSTANTIATIONS_1 // Define a key function for `bad_function_call` in the library, to centralize // its vtable and typeinfo to libc++ rather than having all other libraries // using that class define their own copies. # define _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION # endif # define _LIBCPP_TOSTRING2(x) # x # define _LIBCPP_TOSTRING(x) _LIBCPP_TOSTRING2(x) # if __cplusplus < 201103L # define _LIBCPP_CXX03_LANG # endif # ifndef __has_attribute # define __has_attribute(__x) 0 # endif # ifndef __has_builtin # define __has_builtin(__x) 0 # endif # ifndef __has_extension # define __has_extension(__x) 0 # endif # ifndef __has_feature # define __has_feature(__x) 0 # endif # ifndef __has_cpp_attribute # define __has_cpp_attribute(__x) 0 # endif // '__is_identifier' returns '0' if '__x' is a reserved identifier provided by // the compiler and '1' otherwise. # ifndef __is_identifier # define __is_identifier(__x) 1 # endif # ifndef __has_declspec_attribute # define __has_declspec_attribute(__x) 0 # endif # define __has_keyword(__x) !(__is_identifier(__x)) # ifndef __has_include # define __has_include(...) 0 # endif # if !defined(_LIBCPP_COMPILER_CLANG_BASED) && __cplusplus < 201103L # error "libc++ only supports C++03 with Clang-based compilers. Please enable C++11" # endif # ifdef _LIBCPP_COMPILER_MSVC # error If you successfully use libc++ with MSVC please tell the libc++ developers and consider upstreaming your \ changes. We are not aware of anybody using this configuration and know that at least some code is currently broken. \ If there are users of this configuration we are happy to provide support. # endif // FIXME: ABI detection should be done via compiler builtin macros. This // is just a placeholder until Clang implements such macros. For now assume // that Windows compilers pretending to be MSVC++ target the Microsoft ABI, // and allow the user to explicitly specify the ABI to handle cases where this // heuristic falls short. # if defined(_LIBCPP_ABI_FORCE_ITANIUM) && defined(_LIBCPP_ABI_FORCE_MICROSOFT) # error "Only one of _LIBCPP_ABI_FORCE_ITANIUM and _LIBCPP_ABI_FORCE_MICROSOFT can be defined" # elif defined(_LIBCPP_ABI_FORCE_ITANIUM) # define _LIBCPP_ABI_ITANIUM # elif defined(_LIBCPP_ABI_FORCE_MICROSOFT) # define _LIBCPP_ABI_MICROSOFT # else # if defined(_WIN32) && defined(_MSC_VER) # define _LIBCPP_ABI_MICROSOFT # else # define _LIBCPP_ABI_ITANIUM # endif # endif # if defined(_LIBCPP_ABI_MICROSOFT) && !defined(_LIBCPP_NO_VCRUNTIME) # define _LIBCPP_ABI_VCRUNTIME # endif # if __has_feature(experimental_library) # ifndef _LIBCPP_ENABLE_EXPERIMENTAL # define _LIBCPP_ENABLE_EXPERIMENTAL # endif # endif // Incomplete features get their own specific disabling flags. This makes it // easier to grep for target specific flags once the feature is complete. # if !defined(_LIBCPP_ENABLE_EXPERIMENTAL) && !defined(_LIBCPP_BUILDING_LIBRARY) # define _LIBCPP_HAS_NO_INCOMPLETE_FORMAT # define _LIBCPP_HAS_NO_INCOMPLETE_RANGES # endif // Need to detect which libc we're using if we're on Linux. # if defined(__linux__) # include # if defined(__GLIBC_PREREQ) # define _LIBCPP_GLIBC_PREREQ(a, b) __GLIBC_PREREQ(a, b) # else # define _LIBCPP_GLIBC_PREREQ(a, b) 0 # endif // defined(__GLIBC_PREREQ) # endif // defined(__linux__) # if defined(__MVS__) # include // for __NATIVE_ASCII_F # endif # ifdef __LITTLE_ENDIAN__ # if __LITTLE_ENDIAN__ # define _LIBCPP_LITTLE_ENDIAN # endif // __LITTLE_ENDIAN__ # endif // __LITTLE_ENDIAN__ # ifdef __BIG_ENDIAN__ # if __BIG_ENDIAN__ # define _LIBCPP_BIG_ENDIAN # endif // __BIG_ENDIAN__ # endif // __BIG_ENDIAN__ # ifdef __BYTE_ORDER__ # if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ # define _LIBCPP_LITTLE_ENDIAN # elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ # define _LIBCPP_BIG_ENDIAN # endif // __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ # endif // __BYTE_ORDER__ # ifdef __FreeBSD__ # include # include # if _BYTE_ORDER == _LITTLE_ENDIAN # define _LIBCPP_LITTLE_ENDIAN # else // _BYTE_ORDER == _LITTLE_ENDIAN # define _LIBCPP_BIG_ENDIAN # endif // _BYTE_ORDER == _LITTLE_ENDIAN # endif // __FreeBSD__ # if defined(__NetBSD__) || defined(__OpenBSD__) # include # if _BYTE_ORDER == _LITTLE_ENDIAN # define _LIBCPP_LITTLE_ENDIAN # else // _BYTE_ORDER == _LITTLE_ENDIAN # define _LIBCPP_BIG_ENDIAN # endif // _BYTE_ORDER == _LITTLE_ENDIAN # endif // defined(__NetBSD__) || defined(__OpenBSD__) # if defined(_WIN32) # define _LIBCPP_WIN32API # define _LIBCPP_LITTLE_ENDIAN # define _LIBCPP_SHORT_WCHAR 1 // Both MinGW and native MSVC provide a "MSVC"-like environment # define _LIBCPP_MSVCRT_LIKE // If mingw not explicitly detected, assume using MS C runtime only if // a MS compatibility version is specified. # if defined(_MSC_VER) && !defined(__MINGW32__) # define _LIBCPP_MSVCRT // Using Microsoft's C Runtime library # endif # if (defined(_M_AMD64) || defined(__x86_64__)) || (defined(_M_ARM) || defined(__arm__)) # define _LIBCPP_HAS_BITSCAN64 # endif # define _LIBCPP_HAS_OPEN_WITH_WCHAR # endif // defined(_WIN32) # ifdef __sun__ # include # ifdef _LITTLE_ENDIAN # define _LIBCPP_LITTLE_ENDIAN # else # define _LIBCPP_BIG_ENDIAN # endif # endif // __sun__ # if defined(_AIX) && !defined(__64BIT__) // The size of wchar is 2 byte on 32-bit mode on AIX. # define _LIBCPP_SHORT_WCHAR 1 # endif // Libc++ supports various implementations of std::random_device. // // _LIBCPP_USING_DEV_RANDOM // Read entropy from the given file, by default `/dev/urandom`. // If a token is provided, it is assumed to be the path to a file // to read entropy from. This is the default behavior if nothing // else is specified. This implementation requires storing state // inside `std::random_device`. // // _LIBCPP_USING_ARC4_RANDOM // Use arc4random(). This allows obtaining random data even when // using sandboxing mechanisms. On some platforms like Apple, this // is the recommended source of entropy for user-space programs. // When this option is used, the token passed to `std::random_device`'s // constructor *must* be "/dev/urandom" -- anything else is an error. // // _LIBCPP_USING_GETENTROPY // Use getentropy(). // When this option is used, the token passed to `std::random_device`'s // constructor *must* be "/dev/urandom" -- anything else is an error. // // _LIBCPP_USING_FUCHSIA_CPRNG // Use Fuchsia's zx_cprng_draw() system call, which is specified to // deliver high-quality entropy and cannot fail. // When this option is used, the token passed to `std::random_device`'s // constructor *must* be "/dev/urandom" -- anything else is an error. // // _LIBCPP_USING_NACL_RANDOM // NaCl's sandbox (which PNaCl also runs in) doesn't allow filesystem access, // including accesses to the special files under `/dev`. This implementation // uses the NaCL syscall `nacl_secure_random_init()` to get entropy. // When this option is used, the token passed to `std::random_device`'s // constructor *must* be "/dev/urandom" -- anything else is an error. // // _LIBCPP_USING_WIN32_RANDOM // Use rand_s(), for use on Windows. // When this option is used, the token passed to `std::random_device`'s // constructor *must* be "/dev/urandom" -- anything else is an error. # if defined(__APPLE__) || defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) || \ defined(__DragonFly__) || defined(__sun__) # define _LIBCPP_USING_ARC4_RANDOM # elif defined(__wasi__) || defined(__EMSCRIPTEN__) # define _LIBCPP_USING_GETENTROPY # elif defined(__Fuchsia__) # define _LIBCPP_USING_FUCHSIA_CPRNG # elif defined(__native_client__) # define _LIBCPP_USING_NACL_RANDOM # elif defined(_LIBCPP_WIN32API) # define _LIBCPP_USING_WIN32_RANDOM # else # define _LIBCPP_USING_DEV_RANDOM # endif # if !defined(_LIBCPP_LITTLE_ENDIAN) && !defined(_LIBCPP_BIG_ENDIAN) # include # if __BYTE_ORDER == __LITTLE_ENDIAN # define _LIBCPP_LITTLE_ENDIAN # elif __BYTE_ORDER == __BIG_ENDIAN # define _LIBCPP_BIG_ENDIAN # else // __BYTE_ORDER == __BIG_ENDIAN # error unable to determine endian # endif # endif // !defined(_LIBCPP_LITTLE_ENDIAN) && !defined(_LIBCPP_BIG_ENDIAN) # if __has_attribute(__no_sanitize__) && !defined(_LIBCPP_COMPILER_GCC) # define _LIBCPP_NO_CFI __attribute__((__no_sanitize__("cfi"))) # else # define _LIBCPP_NO_CFI # endif # ifndef _LIBCPP_CXX03_LANG # define _LIBCPP_ALIGNOF(_Tp) alignof(_Tp) # define _ALIGNAS_TYPE(x) alignas(x) # define _ALIGNAS(x) alignas(x) # define _LIBCPP_NORETURN [[noreturn]] # define _NOEXCEPT noexcept # define _NOEXCEPT_(x) noexcept(x) # else # define _LIBCPP_ALIGNOF(_Tp) _Alignof(_Tp) # define _ALIGNAS_TYPE(x) __attribute__((__aligned__(_LIBCPP_ALIGNOF(x)))) # define _ALIGNAS(x) __attribute__((__aligned__(x))) # define _LIBCPP_NORETURN __attribute__((noreturn)) # define _LIBCPP_HAS_NO_NOEXCEPT # define nullptr __nullptr # define _NOEXCEPT throw() # define _NOEXCEPT_(x) typedef __char16_t char16_t; typedef __char32_t char32_t; # endif # if !defined(__cpp_exceptions) || __cpp_exceptions < 199711L # define _LIBCPP_NO_EXCEPTIONS # endif # define _LIBCPP_PREFERRED_ALIGNOF(_Tp) __alignof(_Tp) # if defined(_LIBCPP_COMPILER_CLANG_BASED) # if defined(__APPLE__) && !defined(__i386__) && !defined(__x86_64__) && (!defined(__arm__) || __ARM_ARCH_7K__ >= 2) # define _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT # endif // Objective-C++ features (opt-in) # if __has_feature(objc_arc) # define _LIBCPP_HAS_OBJC_ARC # endif # if __has_feature(objc_arc_weak) # define _LIBCPP_HAS_OBJC_ARC_WEAK # endif # if __has_extension(blocks) # define _LIBCPP_HAS_EXTENSION_BLOCKS # endif # if defined(_LIBCPP_HAS_EXTENSION_BLOCKS) && defined(__APPLE__) # define _LIBCPP_HAS_BLOCKS_RUNTIME # endif # if !__has_feature(address_sanitizer) # define _LIBCPP_HAS_NO_ASAN # endif // Allow for build-time disabling of unsigned integer sanitization # if __has_attribute(no_sanitize) # define _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK __attribute__((__no_sanitize__("unsigned-integer-overflow"))) # endif # define _LIBCPP_ALWAYS_INLINE __attribute__((__always_inline__)) # define _LIBCPP_DISABLE_EXTENSION_WARNING __extension__ # elif defined(_LIBCPP_COMPILER_GCC) # if !defined(__SANITIZE_ADDRESS__) # define _LIBCPP_HAS_NO_ASAN # endif # define _LIBCPP_ALWAYS_INLINE __attribute__((__always_inline__)) # define _LIBCPP_DISABLE_EXTENSION_WARNING __extension__ # elif defined(_LIBCPP_COMPILER_MSVC) # define _LIBCPP_WARNING(x) __pragma(message(__FILE__ "(" _LIBCPP_TOSTRING(__LINE__) ") : warning note: " x)) # if _MSC_VER < 1900 # error "MSVC versions prior to Visual Studio 2015 are not supported" # endif # define _LIBCPP_NORETURN __declspec(noreturn) # define _LIBCPP_WEAK # define _LIBCPP_HAS_NO_ASAN # define _LIBCPP_ALWAYS_INLINE __forceinline # define _LIBCPP_HAS_NO_VECTOR_EXTENSION # define _LIBCPP_DISABLE_EXTENSION_WARNING # endif // _LIBCPP_COMPILER_[CLANG|GCC|MSVC] # if defined(_LIBCPP_OBJECT_FORMAT_COFF) # ifdef _DLL # define _LIBCPP_CRT_FUNC __declspec(dllimport) # else # define _LIBCPP_CRT_FUNC # endif # if defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) || (defined(__MINGW32__) && !defined(_LIBCPP_BUILDING_LIBRARY)) # define _LIBCPP_DLL_VIS # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS # define _LIBCPP_EXPORTED_FROM_ABI # elif defined(_LIBCPP_BUILDING_LIBRARY) # define _LIBCPP_DLL_VIS __declspec(dllexport) # if defined(__MINGW32__) # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS _LIBCPP_DLL_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS # else # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS _LIBCPP_DLL_VIS # endif # define _LIBCPP_OVERRIDABLE_FUNC_VIS _LIBCPP_DLL_VIS # define _LIBCPP_EXPORTED_FROM_ABI __declspec(dllexport) # else # define _LIBCPP_DLL_VIS __declspec(dllimport) # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS _LIBCPP_DLL_VIS # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS # define _LIBCPP_EXPORTED_FROM_ABI __declspec(dllimport) # endif # define _LIBCPP_TYPE_VIS _LIBCPP_DLL_VIS # define _LIBCPP_FUNC_VIS _LIBCPP_DLL_VIS # define _LIBCPP_EXCEPTION_ABI _LIBCPP_DLL_VIS # define _LIBCPP_HIDDEN # define _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS # define _LIBCPP_TEMPLATE_VIS # define _LIBCPP_TEMPLATE_DATA_VIS # define _LIBCPP_ENUM_VIS # else # if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) # define _LIBCPP_VISIBILITY(vis) __attribute__((__visibility__(vis))) # else # define _LIBCPP_VISIBILITY(vis) # endif # define _LIBCPP_HIDDEN _LIBCPP_VISIBILITY("hidden") # define _LIBCPP_FUNC_VIS _LIBCPP_VISIBILITY("default") # define _LIBCPP_TYPE_VIS _LIBCPP_VISIBILITY("default") # define _LIBCPP_TEMPLATE_DATA_VIS _LIBCPP_VISIBILITY("default") # define _LIBCPP_EXPORTED_FROM_ABI _LIBCPP_VISIBILITY("default") # define _LIBCPP_EXCEPTION_ABI _LIBCPP_VISIBILITY("default") # define _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS _LIBCPP_VISIBILITY("default") # define _LIBCPP_CLASS_TEMPLATE_INSTANTIATION_VIS // TODO: Make this a proper customization point or remove the option to override it. # ifndef _LIBCPP_OVERRIDABLE_FUNC_VIS # define _LIBCPP_OVERRIDABLE_FUNC_VIS _LIBCPP_VISIBILITY("default") # endif # if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) // The inline should be removed once PR32114 is resolved # define _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS inline _LIBCPP_HIDDEN # else # define _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS # endif # if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) # if __has_attribute(__type_visibility__) # define _LIBCPP_TEMPLATE_VIS __attribute__((__type_visibility__("default"))) # else # define _LIBCPP_TEMPLATE_VIS __attribute__((__visibility__("default"))) # endif # else # define _LIBCPP_TEMPLATE_VIS # endif # if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) && __has_attribute(__type_visibility__) # define _LIBCPP_ENUM_VIS __attribute__((__type_visibility__("default"))) # else # define _LIBCPP_ENUM_VIS # endif # endif // defined(_LIBCPP_OBJECT_FORMAT_COFF) # if __has_attribute(exclude_from_explicit_instantiation) # define _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION __attribute__((__exclude_from_explicit_instantiation__)) # else // Try to approximate the effect of exclude_from_explicit_instantiation // (which is that entities are not assumed to be provided by explicit // template instantiations in the dylib) by always inlining those entities. # define _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION _LIBCPP_ALWAYS_INLINE # endif // This macro marks a symbol as being hidden from libc++'s ABI. This is achieved // on two levels: // 1. The symbol is given hidden visibility, which ensures that users won't start exporting // symbols from their dynamic library by means of using the libc++ headers. This ensures // that those symbols stay private to the dynamic library in which it is defined. // // 2. The symbol is given an ABI tag that changes with each version of libc++. This ensures // that no ODR violation can arise from mixing two TUs compiled with different versions // of libc++ where we would have changed the definition of a symbol. If the symbols shared // the same name, the ODR would require that their definitions be token-by-token equivalent, // which basically prevents us from being able to make any change to any function in our // headers. Using this ABI tag ensures that the symbol name is "bumped" artificially at // each release, which lets us change the definition of these symbols at our leisure. // Note that historically, this has been achieved in various ways, including force-inlining // all functions or giving internal linkage to all functions. Both these (previous) solutions // suffer from drawbacks that lead notably to code bloat. // // Note that we use _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION to ensure that we don't depend // on _LIBCPP_HIDE_FROM_ABI methods of classes explicitly instantiated in the dynamic library. // // TODO: We provide a escape hatch with _LIBCPP_NO_ABI_TAG for folks who want to avoid increasing // the length of symbols with an ABI tag. In practice, we should remove the escape hatch and // use compression mangling instead, see https://github.com/itanium-cxx-abi/cxx-abi/issues/70. # ifndef _LIBCPP_NO_ABI_TAG # define _LIBCPP_HIDE_FROM_ABI \ _LIBCPP_HIDDEN _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION \ __attribute__((__abi_tag__(_LIBCPP_TOSTRING(_LIBCPP_VERSIONED_IDENTIFIER)))) # else # define _LIBCPP_HIDE_FROM_ABI _LIBCPP_HIDDEN _LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION # endif # ifdef _LIBCPP_BUILDING_LIBRARY # if _LIBCPP_ABI_VERSION > 1 # define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 _LIBCPP_HIDE_FROM_ABI # else # define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 # endif # else # define _LIBCPP_HIDE_FROM_ABI_AFTER_V1 _LIBCPP_HIDE_FROM_ABI # endif // Just so we can migrate to the new macros gradually. # define _LIBCPP_INLINE_VISIBILITY _LIBCPP_HIDE_FROM_ABI // Inline namespaces are available in Clang/GCC/MSVC regardless of C++ dialect. // clang-format off # define _LIBCPP_BEGIN_NAMESPACE_STD namespace std { inline namespace _LIBCPP_ABI_NAMESPACE { # define _LIBCPP_END_NAMESPACE_STD }} # define _VSTD std _LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD # if _LIBCPP_STD_VER > 14 # define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ _LIBCPP_BEGIN_NAMESPACE_STD inline namespace __fs { namespace filesystem { # else # define _LIBCPP_BEGIN_NAMESPACE_FILESYSTEM \ _LIBCPP_BEGIN_NAMESPACE_STD namespace __fs { namespace filesystem { # endif # define _LIBCPP_END_NAMESPACE_FILESYSTEM _LIBCPP_END_NAMESPACE_STD }} // clang-format on # define _VSTD_FS std::__fs::filesystem # if __has_attribute(__enable_if__) # define _LIBCPP_PREFERRED_OVERLOAD __attribute__((__enable_if__(true, ""))) # endif # ifndef __SIZEOF_INT128__ # define _LIBCPP_HAS_NO_INT128 # endif # ifdef _LIBCPP_CXX03_LANG # define static_assert(...) _Static_assert(__VA_ARGS__) # define decltype(...) __decltype(__VA_ARGS__) # endif // _LIBCPP_CXX03_LANG # ifdef _LIBCPP_CXX03_LANG # define _LIBCPP_CONSTEXPR # else # define _LIBCPP_CONSTEXPR constexpr # endif # ifndef __cpp_consteval # define _LIBCPP_CONSTEVAL _LIBCPP_CONSTEXPR # else # define _LIBCPP_CONSTEVAL consteval # endif # ifdef __GNUC__ # define _LIBCPP_NOALIAS __attribute__((__malloc__)) # else # define _LIBCPP_NOALIAS # endif # if __has_attribute(using_if_exists) # define _LIBCPP_USING_IF_EXISTS __attribute__((using_if_exists)) # else # define _LIBCPP_USING_IF_EXISTS # endif # ifdef _LIBCPP_CXX03_LANG # define _LIBCPP_DECLARE_STRONG_ENUM(x) \ struct _LIBCPP_TYPE_VIS x { \ enum __lx // clang-format off # define _LIBCPP_DECLARE_STRONG_ENUM_EPILOG(x) \ __lx __v_; \ _LIBCPP_INLINE_VISIBILITY x(__lx __v) : __v_(__v) {} \ _LIBCPP_INLINE_VISIBILITY explicit x(int __v) : __v_(static_cast<__lx>(__v)) {} \ _LIBCPP_INLINE_VISIBILITY operator int() const { return __v_; } \ }; // clang-format on # else // _LIBCPP_CXX03_LANG # define _LIBCPP_DECLARE_STRONG_ENUM(x) enum class _LIBCPP_ENUM_VIS x # define _LIBCPP_DECLARE_STRONG_ENUM_EPILOG(x) # endif // _LIBCPP_CXX03_LANG # if defined(__APPLE__) || defined(__FreeBSD__) || defined(_LIBCPP_MSVCRT_LIKE) || defined(__sun__) || \ defined(__NetBSD__) # define _LIBCPP_LOCALE__L_EXTENSIONS 1 # endif # ifdef __FreeBSD__ # define _DECLARE_C99_LDBL_MATH 1 # endif // If we are getting operator new from the MSVC CRT, then allocation overloads // for align_val_t were added in 19.12, aka VS 2017 version 15.3. # if defined(_LIBCPP_MSVCRT) && defined(_MSC_VER) && _MSC_VER < 1912 # define _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION # elif defined(_LIBCPP_ABI_VCRUNTIME) && !defined(__cpp_aligned_new) // We're deferring to Microsoft's STL to provide aligned new et al. We don't // have it unless the language feature test macro is defined. # define _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION # elif defined(__MVS__) # define _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION # endif # if defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION) || (!defined(__cpp_aligned_new) || __cpp_aligned_new < 201606) # define _LIBCPP_HAS_NO_ALIGNED_ALLOCATION # endif # if defined(__APPLE__) || defined(__FreeBSD__) # define _LIBCPP_HAS_DEFAULTRUNELOCALE # endif # if defined(__APPLE__) || defined(__FreeBSD__) || defined(__sun__) # define _LIBCPP_WCTYPE_IS_MASK # endif # if _LIBCPP_STD_VER <= 17 || !defined(__cpp_char8_t) # define _LIBCPP_HAS_NO_CHAR8_T # endif // Deprecation macros. // // Deprecations warnings are always enabled, except when users explicitly opt-out // by defining _LIBCPP_DISABLE_DEPRECATION_WARNINGS. # if !defined(_LIBCPP_DISABLE_DEPRECATION_WARNINGS) # if __has_attribute(deprecated) # define _LIBCPP_DEPRECATED __attribute__((deprecated)) # define _LIBCPP_DEPRECATED_(m) __attribute__((deprected(m))) # elif _LIBCPP_STD_VER > 11 # define _LIBCPP_DEPRECATED [[deprecated]] # define _LIBCPP_DEPRECATED_(m) [[deprecated(m)]] # else # define _LIBCPP_DEPRECATED # define _LIBCPP_DEPRECATED_(m) # endif # else # define _LIBCPP_DEPRECATED # define _LIBCPP_DEPRECATED_(m) # endif # if !defined(_LIBCPP_CXX03_LANG) # define _LIBCPP_DEPRECATED_IN_CXX11 _LIBCPP_DEPRECATED # else # define _LIBCPP_DEPRECATED_IN_CXX11 # endif # if _LIBCPP_STD_VER > 11 # define _LIBCPP_DEPRECATED_IN_CXX14 _LIBCPP_DEPRECATED # else # define _LIBCPP_DEPRECATED_IN_CXX14 # endif # if _LIBCPP_STD_VER > 14 # define _LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_DEPRECATED # else # define _LIBCPP_DEPRECATED_IN_CXX17 # endif # if _LIBCPP_STD_VER > 17 # define _LIBCPP_DEPRECATED_IN_CXX20 _LIBCPP_DEPRECATED # else # define _LIBCPP_DEPRECATED_IN_CXX20 # endif # if !defined(_LIBCPP_HAS_NO_CHAR8_T) # define _LIBCPP_DEPRECATED_WITH_CHAR8_T _LIBCPP_DEPRECATED # else # define _LIBCPP_DEPRECATED_WITH_CHAR8_T # endif // Macros to enter and leave a state where deprecation warnings are suppressed. # if defined(_LIBCPP_COMPILER_CLANG_BASED) || defined(_LIBCPP_COMPILER_GCC) # define _LIBCPP_SUPPRESS_DEPRECATED_PUSH \ _Pragma("GCC diagnostic push") _Pragma("GCC diagnostic ignored \"-Wdeprecated\"") \ _Pragma("GCC diagnostic ignored \"-Wdeprecated-declarations\"") # define _LIBCPP_SUPPRESS_DEPRECATED_POP _Pragma("GCC diagnostic pop") # else # define _LIBCPP_SUPPRESS_DEPRECATED_PUSH # define _LIBCPP_SUPPRESS_DEPRECATED_POP # endif # if _LIBCPP_STD_VER <= 11 # define _LIBCPP_EXPLICIT_AFTER_CXX11 # else # define _LIBCPP_EXPLICIT_AFTER_CXX11 explicit # endif # if _LIBCPP_STD_VER > 11 # define _LIBCPP_CONSTEXPR_AFTER_CXX11 constexpr # else # define _LIBCPP_CONSTEXPR_AFTER_CXX11 # endif # if _LIBCPP_STD_VER > 14 # define _LIBCPP_CONSTEXPR_AFTER_CXX14 constexpr # else # define _LIBCPP_CONSTEXPR_AFTER_CXX14 # endif # if _LIBCPP_STD_VER > 17 # define _LIBCPP_CONSTEXPR_AFTER_CXX17 constexpr # else # define _LIBCPP_CONSTEXPR_AFTER_CXX17 # endif # if __has_cpp_attribute(nodiscard) || defined(_LIBCPP_COMPILER_MSVC) # define _LIBCPP_NODISCARD [[nodiscard]] # elif defined(_LIBCPP_COMPILER_CLANG_BASED) && !defined(_LIBCPP_CXX03_LANG) # define _LIBCPP_NODISCARD [[clang::warn_unused_result]] # else // We can't use GCC's [[gnu::warn_unused_result]] and // __attribute__((warn_unused_result)), because GCC does not silence them via // (void) cast. # define _LIBCPP_NODISCARD # endif // _LIBCPP_NODISCARD_EXT may be used to apply [[nodiscard]] to entities not // specified as such as an extension. # if defined(_LIBCPP_ENABLE_NODISCARD) && !defined(_LIBCPP_DISABLE_NODISCARD_EXT) # define _LIBCPP_NODISCARD_EXT _LIBCPP_NODISCARD # else # define _LIBCPP_NODISCARD_EXT # endif # if !defined(_LIBCPP_DISABLE_NODISCARD_AFTER_CXX17) && (_LIBCPP_STD_VER > 17 || defined(_LIBCPP_ENABLE_NODISCARD)) # define _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_NODISCARD # else # define _LIBCPP_NODISCARD_AFTER_CXX17 # endif # if __has_attribute(no_destroy) # define _LIBCPP_NO_DESTROY __attribute__((__no_destroy__)) # else # define _LIBCPP_NO_DESTROY # endif # ifndef _LIBCPP_HAS_NO_ASAN extern "C" _LIBCPP_FUNC_VIS void __sanitizer_annotate_contiguous_container(const void*, const void*, const void*, const void*); # endif // Try to find out if RTTI is disabled. # if !defined(__cpp_rtti) || __cpp_rtti < 199711L # define _LIBCPP_NO_RTTI # endif # ifndef _LIBCPP_WEAK # define _LIBCPP_WEAK __attribute__((__weak__)) # endif // Thread API // clang-format off # if !defined(_LIBCPP_HAS_NO_THREADS) && \ !defined(_LIBCPP_HAS_THREAD_API_PTHREAD) && \ !defined(_LIBCPP_HAS_THREAD_API_WIN32) && \ !defined(_LIBCPP_HAS_THREAD_API_EXTERNAL) # if defined(__FreeBSD__) || \ defined(__wasi__) || \ defined(__NetBSD__) || \ defined(__OpenBSD__) || \ defined(__NuttX__) || \ defined(__linux__) || \ defined(__GNU__) || \ defined(__APPLE__) || \ defined(__sun__) || \ defined(__MVS__) || \ defined(_AIX) || \ defined(__EMSCRIPTEN__) // clang-format on # define _LIBCPP_HAS_THREAD_API_PTHREAD # elif defined(__Fuchsia__) // TODO(44575): Switch to C11 thread API when possible. # define _LIBCPP_HAS_THREAD_API_PTHREAD # elif defined(_LIBCPP_WIN32API) # define _LIBCPP_HAS_THREAD_API_WIN32 # else # error "No thread API" # endif // _LIBCPP_HAS_THREAD_API # endif // _LIBCPP_HAS_NO_THREADS # if defined(_LIBCPP_HAS_THREAD_API_PTHREAD) # if defined(__ANDROID__) && __ANDROID_API__ >= 30 # define _LIBCPP_HAS_COND_CLOCKWAIT # elif defined(_LIBCPP_GLIBC_PREREQ) # if _LIBCPP_GLIBC_PREREQ(2, 30) # define _LIBCPP_HAS_COND_CLOCKWAIT # endif # endif # endif # if defined(_LIBCPP_HAS_NO_THREADS) && defined(_LIBCPP_HAS_THREAD_API_PTHREAD) # error _LIBCPP_HAS_THREAD_API_PTHREAD may only be defined when \ _LIBCPP_HAS_NO_THREADS is not defined. # endif # if defined(_LIBCPP_HAS_NO_THREADS) && defined(_LIBCPP_HAS_THREAD_API_EXTERNAL) # error _LIBCPP_HAS_THREAD_API_EXTERNAL may not be defined when \ _LIBCPP_HAS_NO_THREADS is defined. # endif # if defined(_LIBCPP_HAS_NO_MONOTONIC_CLOCK) && !defined(_LIBCPP_HAS_NO_THREADS) # error _LIBCPP_HAS_NO_MONOTONIC_CLOCK may only be defined when \ _LIBCPP_HAS_NO_THREADS is defined. # endif # if !defined(_LIBCPP_HAS_NO_THREADS) && !defined(__STDCPP_THREADS__) # define __STDCPP_THREADS__ 1 # endif // The glibc and Bionic implementation of pthreads implements // pthread_mutex_destroy as nop for regular mutexes. Additionally, Win32 // mutexes have no destroy mechanism. // // This optimization can't be performed on Apple platforms, where // pthread_mutex_destroy can allow the kernel to release resources. // See https://llvm.org/D64298 for details. // // TODO(EricWF): Enable this optimization on Bionic after speaking to their // respective stakeholders. // clang-format off # if (defined(_LIBCPP_HAS_THREAD_API_PTHREAD) && defined(__GLIBC__)) || \ (defined(_LIBCPP_HAS_THREAD_API_C11) && defined(__Fuchsia__)) || \ defined(_LIBCPP_HAS_THREAD_API_WIN32) // clang-format on # define _LIBCPP_HAS_TRIVIAL_MUTEX_DESTRUCTION # endif // Destroying a condvar is a nop on Windows. // // This optimization can't be performed on Apple platforms, where // pthread_cond_destroy can allow the kernel to release resources. // See https://llvm.org/D64298 for details. // // TODO(EricWF): This is potentially true for some pthread implementations // as well. # if (defined(_LIBCPP_HAS_THREAD_API_C11) && defined(__Fuchsia__)) || defined(_LIBCPP_HAS_THREAD_API_WIN32) # define _LIBCPP_HAS_TRIVIAL_CONDVAR_DESTRUCTION # endif // Some systems do not provide gets() in their C library, for security reasons. # if defined(_LIBCPP_MSVCRT) || (defined(__FreeBSD_version) && __FreeBSD_version >= 1300043) || defined(__OpenBSD__) # define _LIBCPP_C_HAS_NO_GETS # endif # if defined(__BIONIC__) || defined(__NuttX__) || defined(__Fuchsia__) || defined(__wasi__) || \ defined(_LIBCPP_HAS_MUSL_LIBC) || defined(__OpenBSD__) # define _LIBCPP_PROVIDES_DEFAULT_RUNE_TABLE # endif # if __has_feature(cxx_atomic) || __has_extension(c_atomic) || __has_keyword(_Atomic) # define _LIBCPP_HAS_C_ATOMIC_IMP # elif defined(_LIBCPP_COMPILER_GCC) # define _LIBCPP_HAS_GCC_ATOMIC_IMP # endif # if !defined(_LIBCPP_HAS_C_ATOMIC_IMP) && !defined(_LIBCPP_HAS_GCC_ATOMIC_IMP) && \ !defined(_LIBCPP_HAS_EXTERNAL_ATOMIC_IMP) # define _LIBCPP_HAS_NO_ATOMIC_HEADER # else # ifndef _LIBCPP_ATOMIC_FLAG_TYPE # define _LIBCPP_ATOMIC_FLAG_TYPE bool # endif # ifdef _LIBCPP_FREESTANDING # define _LIBCPP_ATOMIC_ONLY_USE_BUILTINS # endif # endif # ifndef _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK # define _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK # endif # if defined(_LIBCPP_ENABLE_THREAD_SAFETY_ANNOTATIONS) # if defined(__clang__) && __has_attribute(acquire_capability) // Work around the attribute handling in clang. When both __declspec and // __attribute__ are present, the processing goes awry preventing the definition // of the types. In MinGW mode, __declspec evaluates to __attribute__, and thus // combining the two does work. # if !defined(_MSC_VER) # define _LIBCPP_HAS_THREAD_SAFETY_ANNOTATIONS # endif # endif # endif # ifdef _LIBCPP_HAS_THREAD_SAFETY_ANNOTATIONS # define _LIBCPP_THREAD_SAFETY_ANNOTATION(x) __attribute__((x)) # else # define _LIBCPP_THREAD_SAFETY_ANNOTATION(x) # endif # if _LIBCPP_STD_VER > 17 # define _LIBCPP_CONSTINIT constinit # elif __has_attribute(require_constant_initialization) # define _LIBCPP_CONSTINIT __attribute__((__require_constant_initialization__)) # else # define _LIBCPP_CONSTINIT # endif # if __has_attribute(diagnose_if) && !defined(_LIBCPP_DISABLE_ADDITIONAL_DIAGNOSTICS) # define _LIBCPP_DIAGNOSE_WARNING(...) __attribute__((diagnose_if(__VA_ARGS__, "warning"))) # define _LIBCPP_DIAGNOSE_ERROR(...) __attribute__((diagnose_if(__VA_ARGS__, "error"))) # else # define _LIBCPP_DIAGNOSE_WARNING(...) # define _LIBCPP_DIAGNOSE_ERROR(...) # endif // Use a function like macro to imply that it must be followed by a semicolon # if __has_cpp_attribute(fallthrough) # define _LIBCPP_FALLTHROUGH() [[fallthrough]] # elif __has_attribute(__fallthrough__) # define _LIBCPP_FALLTHROUGH() __attribute__((__fallthrough__)) # else # define _LIBCPP_FALLTHROUGH() ((void)0) # endif # if __has_attribute(__nodebug__) # define _LIBCPP_NODEBUG __attribute__((__nodebug__)) # else # define _LIBCPP_NODEBUG # endif # if __has_attribute(__standalone_debug__) # define _LIBCPP_STANDALONE_DEBUG __attribute__((__standalone_debug__)) # else # define _LIBCPP_STANDALONE_DEBUG # endif # if __has_attribute(__preferred_name__) # define _LIBCPP_PREFERRED_NAME(x) __attribute__((__preferred_name__(x))) # else # define _LIBCPP_PREFERRED_NAME(x) # endif // We often repeat things just for handling wide characters in the library. // When wide characters are disabled, it can be useful to have a quick way of // disabling it without having to resort to #if-#endif, which has a larger // impact on readability. # if defined(_LIBCPP_HAS_NO_WIDE_CHARACTERS) # define _LIBCPP_IF_WIDE_CHARACTERS(...) # else # define _LIBCPP_IF_WIDE_CHARACTERS(...) __VA_ARGS__ # endif # if defined(_LIBCPP_ABI_MICROSOFT) && (defined(_LIBCPP_COMPILER_MSVC) || __has_declspec_attribute(empty_bases)) # define _LIBCPP_DECLSPEC_EMPTY_BASES __declspec(empty_bases) # else # define _LIBCPP_DECLSPEC_EMPTY_BASES # endif # if defined(_LIBCPP_ENABLE_CXX17_REMOVED_FEATURES) # define _LIBCPP_ENABLE_CXX17_REMOVED_AUTO_PTR # define _LIBCPP_ENABLE_CXX17_REMOVED_BINDERS # define _LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE # define _LIBCPP_ENABLE_CXX17_REMOVED_UNEXPECTED_FUNCTIONS # define _LIBCPP_ENABLE_CXX17_REMOVED_UNARY_BINARY_FUNCTION # endif // _LIBCPP_ENABLE_CXX17_REMOVED_FEATURES // Leave the deprecation notices in by default, but don't remove unary_function and // binary_function entirely just yet. That way, folks will have one release to act // on the deprecation warnings. # ifndef _LIBCPP_ENABLE_CXX17_REMOVED_UNARY_BINARY_FUNCTION # define _LIBCPP_ENABLE_CXX17_REMOVED_UNARY_BINARY_FUNCTION # endif # if defined(_LIBCPP_ENABLE_CXX20_REMOVED_FEATURES) # define _LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_MEMBERS # define _LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_VOID_SPECIALIZATION # define _LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS # define _LIBCPP_ENABLE_CXX20_REMOVED_NEGATORS # define _LIBCPP_ENABLE_CXX20_REMOVED_RAW_STORAGE_ITERATOR # define _LIBCPP_ENABLE_CXX20_REMOVED_TYPE_TRAITS # endif // _LIBCPP_ENABLE_CXX20_REMOVED_FEATURES # if !defined(__cpp_impl_coroutine) || __cpp_impl_coroutine < 201902L # define _LIBCPP_HAS_NO_CXX20_COROUTINES # endif # define _LIBCPP_PUSH_MACROS _Pragma("push_macro(\"min\")") _Pragma("push_macro(\"max\")") # define _LIBCPP_POP_MACROS _Pragma("pop_macro(\"min\")") _Pragma("pop_macro(\"max\")") # ifndef _LIBCPP_NO_AUTO_LINK # if defined(_LIBCPP_ABI_MICROSOFT) && !defined(_LIBCPP_BUILDING_LIBRARY) # if !defined(_LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS) # pragma comment(lib, "c++.lib") # else # pragma comment(lib, "libc++.lib") # endif # endif // defined(_LIBCPP_ABI_MICROSOFT) && !defined(_LIBCPP_BUILDING_LIBRARY) # endif // _LIBCPP_NO_AUTO_LINK // Configures the fopen close-on-exec mode character, if any. This string will // be appended to any mode string used by fstream for fopen/fdopen. // // Not all platforms support this, but it helps avoid fd-leaks on platforms that // do. # if defined(__BIONIC__) # define _LIBCPP_FOPEN_CLOEXEC_MODE "e" # else # define _LIBCPP_FOPEN_CLOEXEC_MODE # endif // Support for _FILE_OFFSET_BITS=64 landed gradually in Android, so the full set // of functions used in cstdio may not be available for low API levels when // using 64-bit file offsets on LP32. # if defined(__BIONIC__) && defined(__USE_FILE_OFFSET64) && __ANDROID_API__ < 24 # define _LIBCPP_HAS_NO_FGETPOS_FSETPOS # endif # if __has_attribute(init_priority) // TODO: Remove this once we drop support for building libc++ with old Clangs # if (defined(_LIBCPP_CLANG_VER) && _LIBCPP_CLANG_VER < 1200) || \ (defined(__apple_build_version__) && __apple_build_version__ < 13000000) # define _LIBCPP_INIT_PRIORITY_MAX __attribute__((init_priority(101))) # else # define _LIBCPP_INIT_PRIORITY_MAX __attribute__((init_priority(100))) # endif # else # define _LIBCPP_INIT_PRIORITY_MAX # endif # if defined(__GNUC__) || defined(__clang__) // The attribute uses 1-based indices for ordinary and static member functions. // The attribute uses 2-based indices for non-static member functions. # define _LIBCPP_ATTRIBUTE_FORMAT(archetype, format_string_index, first_format_arg_index) \ __attribute__((__format__(archetype, format_string_index, first_format_arg_index))) # else # define _LIBCPP_ATTRIBUTE_FORMAT(archetype, format_string_index, first_format_arg_index) /* nothing */ # endif # if __has_cpp_attribute(msvc::no_unique_address) // MSVC implements [[no_unique_address]] as a silent no-op currently. // (If/when MSVC breaks its C++ ABI, it will be changed to work as intended.) // However, MSVC implements [[msvc::no_unique_address]] which does what // [[no_unique_address]] is supposed to do, in general. // Clang-cl does not yet (14.0) implement either [[no_unique_address]] or // [[msvc::no_unique_address]] though. If/when it does implement // [[msvc::no_unique_address]], this should be preferred though. # define _LIBCPP_NO_UNIQUE_ADDRESS [[msvc::no_unique_address]] # elif __has_cpp_attribute(no_unique_address) # define _LIBCPP_NO_UNIQUE_ADDRESS [[no_unique_address]] # else # define _LIBCPP_NO_UNIQUE_ADDRESS /* nothing */ // Note that this can be replaced by #error as soon as clang-cl // implements msvc::no_unique_address, since there should be no C++20 // compiler that doesn't support one of the two attributes at that point. // We generally don't want to use this macro outside of C++20-only code, // because using it conditionally in one language version only would make // the ABI inconsistent. # endif # ifdef _LIBCPP_COMPILER_CLANG_BASED # define _LIBCPP_DIAGNOSTIC_PUSH _Pragma("clang diagnostic push") # define _LIBCPP_DIAGNOSTIC_POP _Pragma("clang diagnostic pop") # define _LIBCPP_CLANG_DIAGNOSTIC_IGNORED(str) _Pragma(_LIBCPP_TOSTRING(clang diagnostic ignored str)) # define _LIBCPP_GCC_DIAGNOSTIC_IGNORED(str) # elif defined(_LIBCPP_COMPILER_GCC) # define _LIBCPP_DIAGNOSTIC_PUSH _Pragma("GCC diagnostic push") # define _LIBCPP_DIAGNOSTIC_POP _Pragma("GCC diagnostic pop") # define _LIBCPP_CLANG_DIAGNOSTIC_IGNORED(str) # define _LIBCPP_GCC_DIAGNOSTIC_IGNORED(str) _Pragma(_LIBCPP_TOSTRING(GCC diagnostic ignored str)) # else # define _LIBCPP_DIAGNOSTIC_PUSH # define _LIBCPP_DIAGNOSTIC_POP # define _LIBCPP_CLANG_DIAGNOSTIC_IGNORED(str) # define _LIBCPP_GCC_DIAGNOSTIC_IGNORED(str) # endif # if defined(_AIX) && !defined(_LIBCPP_COMPILER_GCC) # define _LIBCPP_PACKED_BYTE_FOR_AIX _Pragma("pack(1)") # define _LIBCPP_PACKED_BYTE_FOR_AIX_END _Pragma("pack(pop)") # else # define _LIBCPP_PACKED_BYTE_FOR_AIX /* empty */ # define _LIBCPP_PACKED_BYTE_FOR_AIX_END /* empty */ # endif # if __has_attribute(__packed__) # define _LIBCPP_PACKED __attribute__((__packed__)) # else # define _LIBCPP_PACKED # endif #endif // __cplusplus #endif // _LIBCPP___CONFIG diff --git a/libcxx/include/vector b/libcxx/include/vector index 252a0f051ff5..63759407ce94 100644 --- a/libcxx/include/vector +++ b/libcxx/include/vector @@ -1,3323 +1,3370 @@ // -*- C++ -*- //===----------------------------------------------------------------------===// // // 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 // //===----------------------------------------------------------------------===// #ifndef _LIBCPP_VECTOR #define _LIBCPP_VECTOR /* vector synopsis namespace std { template > class vector { public: typedef T value_type; typedef Allocator allocator_type; typedef typename allocator_type::reference reference; typedef typename allocator_type::const_reference const_reference; typedef implementation-defined iterator; typedef implementation-defined const_iterator; typedef typename allocator_type::size_type size_type; typedef typename allocator_type::difference_type difference_type; typedef typename allocator_type::pointer pointer; typedef typename allocator_type::const_pointer const_pointer; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; vector() noexcept(is_nothrow_default_constructible::value); explicit vector(const allocator_type&); explicit vector(size_type n); explicit vector(size_type n, const allocator_type&); // C++14 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); template vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); vector(const vector& x); vector(vector&& x) noexcept(is_nothrow_move_constructible::value); vector(initializer_list il); vector(initializer_list il, const allocator_type& a); ~vector(); vector& operator=(const vector& x); vector& operator=(vector&& x) noexcept( allocator_type::propagate_on_container_move_assignment::value || allocator_type::is_always_equal::value); // C++17 vector& operator=(initializer_list il); template void assign(InputIterator first, InputIterator last); void assign(size_type n, const value_type& u); void assign(initializer_list il); allocator_type get_allocator() const noexcept; iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; size_type capacity() const noexcept; bool empty() const noexcept; void reserve(size_type n); void shrink_to_fit() noexcept; reference operator[](size_type n); const_reference operator[](size_type n) const; reference at(size_type n); const_reference at(size_type n) const; reference front(); const_reference front() const; reference back(); const_reference back() const; value_type* data() noexcept; const value_type* data() const noexcept; void push_back(const value_type& x); void push_back(value_type&& x); template reference emplace_back(Args&&... args); // reference in C++17 void pop_back(); template iterator emplace(const_iterator position, Args&&... args); iterator insert(const_iterator position, const value_type& x); iterator insert(const_iterator position, value_type&& x); iterator insert(const_iterator position, size_type n, const value_type& x); template iterator insert(const_iterator position, InputIterator first, InputIterator last); iterator insert(const_iterator position, initializer_list il); iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last); void clear() noexcept; void resize(size_type sz); void resize(size_type sz, const value_type& c); void swap(vector&) noexcept(allocator_traits::propagate_on_container_swap::value || allocator_traits::is_always_equal::value); // C++17 bool __invariants() const; }; template > class vector { public: typedef bool value_type; typedef Allocator allocator_type; typedef implementation-defined iterator; typedef implementation-defined const_iterator; typedef typename allocator_type::size_type size_type; typedef typename allocator_type::difference_type difference_type; typedef iterator pointer; typedef const_iterator const_pointer; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; class reference { public: reference(const reference&) noexcept; operator bool() const noexcept; reference& operator=(bool x) noexcept; reference& operator=(const reference& x) noexcept; iterator operator&() const noexcept; void flip() noexcept; }; class const_reference { public: const_reference(const reference&) noexcept; operator bool() const noexcept; const_iterator operator&() const noexcept; }; vector() noexcept(is_nothrow_default_constructible::value); explicit vector(const allocator_type&); explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); template vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); vector(const vector& x); vector(vector&& x) noexcept(is_nothrow_move_constructible::value); vector(initializer_list il); vector(initializer_list il, const allocator_type& a); ~vector(); vector& operator=(const vector& x); vector& operator=(vector&& x) noexcept( allocator_type::propagate_on_container_move_assignment::value || allocator_type::is_always_equal::value); // C++17 vector& operator=(initializer_list il); template void assign(InputIterator first, InputIterator last); void assign(size_type n, const value_type& u); void assign(initializer_list il); allocator_type get_allocator() const noexcept; iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; size_type capacity() const noexcept; bool empty() const noexcept; void reserve(size_type n); void shrink_to_fit() noexcept; reference operator[](size_type n); const_reference operator[](size_type n) const; reference at(size_type n); const_reference at(size_type n) const; reference front(); const_reference front() const; reference back(); const_reference back() const; void push_back(const value_type& x); template reference emplace_back(Args&&... args); // C++14; reference in C++17 void pop_back(); template iterator emplace(const_iterator position, Args&&... args); // C++14 iterator insert(const_iterator position, const value_type& x); iterator insert(const_iterator position, size_type n, const value_type& x); template iterator insert(const_iterator position, InputIterator first, InputIterator last); iterator insert(const_iterator position, initializer_list il); iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last); void clear() noexcept; void resize(size_type sz); void resize(size_type sz, value_type x); void swap(vector&) noexcept(allocator_traits::propagate_on_container_swap::value || allocator_traits::is_always_equal::value); // C++17 void flip() noexcept; bool __invariants() const; }; template ::value_type>> vector(InputIterator, InputIterator, Allocator = Allocator()) -> vector::value_type, Allocator>; // C++17 template struct hash>; template bool operator==(const vector& x, const vector& y); template bool operator< (const vector& x, const vector& y); template bool operator!=(const vector& x, const vector& y); template bool operator> (const vector& x, const vector& y); template bool operator>=(const vector& x, const vector& y); template bool operator<=(const vector& x, const vector& y); template void swap(vector& x, vector& y) noexcept(noexcept(x.swap(y))); template typename vector::size_type erase(vector& c, const U& value); // C++20 template typename vector::size_type erase_if(vector& c, Predicate pred); // C++20 } // std */ #include <__algorithm/copy.h> #include <__algorithm/equal.h> #include <__algorithm/fill_n.h> #include <__algorithm/lexicographical_compare.h> #include <__algorithm/remove.h> #include <__algorithm/remove_if.h> #include <__algorithm/rotate.h> #include <__algorithm/unwrap_iter.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__bit_reference> #include <__config> #include <__debug> #include <__format/enable_insertable.h> #include <__functional/hash.h> #include <__functional/unary_function.h> #include <__iterator/advance.h> #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__iterator/wrap_iter.h> #include <__memory/allocate_at_least.h> #include <__memory/pointer_traits.h> #include <__memory/swap_allocator.h> #include <__split_buffer> #include <__utility/forward.h> #include <__utility/move.h> #include <__utility/swap.h> +#include <__utility/transaction.h> #include #include #include #include // for forward declaration of vector #include #include #include #include #include #ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES # include # include # include #endif // standard-mandated includes // [iterator.range] #include <__iterator/access.h> #include <__iterator/data.h> #include <__iterator/empty.h> #include <__iterator/reverse_access.h> #include <__iterator/size.h> // [vector.syn] #include #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif _LIBCPP_PUSH_MACROS #include <__undef_macros> _LIBCPP_BEGIN_NAMESPACE_STD template */> class _LIBCPP_TEMPLATE_VIS vector { private: typedef allocator<_Tp> __default_allocator_type; public: typedef vector __self; typedef _Tp value_type; typedef _Allocator allocator_type; typedef allocator_traits __alloc_traits; typedef value_type& reference; typedef const value_type& const_reference; typedef typename __alloc_traits::size_type size_type; typedef typename __alloc_traits::difference_type difference_type; typedef typename __alloc_traits::pointer pointer; typedef typename __alloc_traits::const_pointer const_pointer; typedef __wrap_iter iterator; typedef __wrap_iter const_iterator; typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; static_assert((is_same::value), "Allocator::value_type must be same type as value_type"); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector() _NOEXCEPT_(is_nothrow_default_constructible::value) { _VSTD::__debug_db_insert_c(this); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) #if _LIBCPP_STD_VER <= 14 _NOEXCEPT_(is_nothrow_copy_constructible::value) #else _NOEXCEPT #endif : __end_cap_(nullptr, __a) { _VSTD::__debug_db_insert_c(this); } _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(size_type __n); #if _LIBCPP_STD_VER > 11 _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(size_type __n, const allocator_type& __a); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(size_type __n, const value_type& __x); template ::value> > _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(size_type __n, const value_type& __x, const allocator_type& __a) : __end_cap_(nullptr, __a) { _VSTD::__debug_db_insert_c(this); if (__n > 0) { __vallocate(__n); __construct_at_end(__n, __x); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_InputIterator __first, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value, _InputIterator>::type __last); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_ForwardIterator __first, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value, _ForwardIterator>::type __last); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); - _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY - ~vector() - { - __annotate_delete(); - std::__debug_db_erase_c(this); +private: + class __destroy_vector { + public: + _LIBCPP_CONSTEXPR __destroy_vector(vector& __vec) : __vec_(__vec) {} - if (this->__begin_ != nullptr) - { - __clear(); - __alloc_traits::deallocate(__alloc(), this->__begin_, capacity()); + _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI void operator()() { + __vec_.__annotate_delete(); + std::__debug_db_erase_c(std::addressof(__vec_)); + + if (__vec_.__begin_ != nullptr) { + __vec_.__clear(); + __alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity()); + } } - } + + private: + vector& __vec_; + }; + +public: + _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector(*this)(); } _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(const vector& __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(const vector& __x, const __type_identity_t& __a); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector& operator=(const vector& __x); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector(initializer_list __il); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector(initializer_list __il, const allocator_type& __a); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector& operator=(initializer_list __il) {assign(__il.begin(), __il.end()); return *this;} #endif // !_LIBCPP_CXX03_LANG _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector(vector&& __x) #if _LIBCPP_STD_VER > 14 noexcept; #else _NOEXCEPT_(is_nothrow_move_constructible::value); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector(vector&& __x, const __type_identity_t& __a); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY vector& operator=(vector&& __x) _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value, void >::type assign(_InputIterator __first, _InputIterator __last); template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value, void >::type assign(_ForwardIterator __first, _ForwardIterator __last); _LIBCPP_CONSTEXPR_AFTER_CXX17 void assign(size_type __n, const_reference __u); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void assign(initializer_list __il) {assign(__il.begin(), __il.end());} #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT {return this->__alloc();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rbegin() const _NOEXCEPT {return const_reverse_iterator(end());} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rend() const _NOEXCEPT {return const_reverse_iterator(begin());} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_iterator cbegin() const _NOEXCEPT {return begin();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_iterator cend() const _NOEXCEPT {return end();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crend() const _NOEXCEPT {return rend();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT {return static_cast(this->__end_ - this->__begin_);} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT {return static_cast(__end_cap() - this->__begin_);} _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return this->__begin_ == this->__end_;} _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type max_size() const _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 void reserve(size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 void shrink_to_fit() _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 reference at(size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reference at(size_type __n) const; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY reference front() _NOEXCEPT { _LIBCPP_ASSERT(!empty(), "front() called on an empty vector"); return *this->__begin_; } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reference front() const _NOEXCEPT { _LIBCPP_ASSERT(!empty(), "front() called on an empty vector"); return *this->__begin_; } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY reference back() _NOEXCEPT { _LIBCPP_ASSERT(!empty(), "back() called on an empty vector"); return *(this->__end_ - 1); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_reference back() const _NOEXCEPT { _LIBCPP_ASSERT(!empty(), "back() called on an empty vector"); return *(this->__end_ - 1); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY value_type* data() _NOEXCEPT {return _VSTD::__to_address(this->__begin_);} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const value_type* data() const _NOEXCEPT {return _VSTD::__to_address(this->__begin_);} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); template _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY #if _LIBCPP_STD_VER > 14 reference emplace_back(_Args&&... __args); #else void emplace_back(_Args&&... __args); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void pop_back(); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, const_reference __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, value_type&& __x); template _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator emplace(const_iterator __position, _Args&&... __args); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, size_type __n, const_reference __x); template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value, iterator >::type insert(const_iterator __position, _InputIterator __first, _InputIterator __last); template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value, iterator >::type insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __position, initializer_list __il) {return insert(__position, __il.begin(), __il.end());} #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator erase(const_iterator __first, const_iterator __last); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT { size_type __old_size = size(); __clear(); __annotate_shrink(__old_size); std::__debug_db_invalidate_all(this); } _LIBCPP_CONSTEXPR_AFTER_CXX17 void resize(size_type __sz); _LIBCPP_CONSTEXPR_AFTER_CXX17 void resize(size_type __sz, const_reference __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 void swap(vector&) #if _LIBCPP_STD_VER >= 14 _NOEXCEPT; #else _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable::value); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 bool __invariants() const; #ifdef _LIBCPP_ENABLE_DEBUG_MODE bool __dereferenceable(const const_iterator* __i) const; bool __decrementable(const const_iterator* __i) const; bool __addable(const const_iterator* __i, ptrdiff_t __n) const; bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; #endif // _LIBCPP_ENABLE_DEBUG_MODE private: pointer __begin_ = nullptr; pointer __end_ = nullptr; __compressed_pair __end_cap_ = __compressed_pair(nullptr, __default_init_tag()); _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last); // Allocate space for __n objects // throws length_error if __n > max_size() // throws (probably bad_alloc) if memory run out // Precondition: __begin_ == __end_ == __end_cap() == 0 // Precondition: __n > 0 // Postcondition: capacity() >= __n // Postcondition: size() == 0 _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) { if (__n > max_size()) __throw_length_error(); auto __allocation = std::__allocate_at_least(__alloc(), __n); __begin_ = __allocation.ptr; __end_ = __allocation.ptr; __end_cap() = __begin_ + __allocation.count; __annotate_new(0); } _LIBCPP_CONSTEXPR_AFTER_CXX17 void __vdeallocate() _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; _LIBCPP_CONSTEXPR_AFTER_CXX17 void __construct_at_end(size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, const_reference __x); template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __append(size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __append(size_type __n, const_reference __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(pointer __p) _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 void __swap_out_circular_buffer(__split_buffer& __v); _LIBCPP_CONSTEXPR_AFTER_CXX17 pointer __swap_out_circular_buffer(__split_buffer& __v, pointer __p); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_range(pointer __from_s, pointer __from_e, pointer __to); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign(vector& __c, false_type) _NOEXCEPT_(__alloc_traits::is_always_equal::value); _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(pointer __new_last) _NOEXCEPT { if (!__libcpp_is_constant_evaluated()) __invalidate_iterators_past(__new_last); size_type __old_size = size(); __base_destruct_at_end(__new_last); __annotate_shrink(__old_size); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY inline void __push_back_slow_path(_Up&& __x); template _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY inline void __emplace_back_slow_path(_Args&&... __args); // The following functions are no-ops outside of AddressSanitizer mode. // We call annotatations only for the default Allocator because other allocators // may not meet the AddressSanitizer alignment constraints. // See the documentation for __sanitizer_annotate_contiguous_container for more details. #ifndef _LIBCPP_HAS_NO_ASAN _LIBCPP_CONSTEXPR_AFTER_CXX17 void __annotate_contiguous_container(const void *__beg, const void *__end, const void *__old_mid, const void *__new_mid) const { if (!__libcpp_is_constant_evaluated() && __beg && is_same::value) __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); } #else _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __annotate_contiguous_container(const void*, const void*, const void*, const void*) const _NOEXCEPT {} #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __annotate_new(size_type __current_size) const _NOEXCEPT { __annotate_contiguous_container(data(), data() + capacity(), data() + capacity(), data() + __current_size); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __annotate_delete() const _NOEXCEPT { __annotate_contiguous_container(data(), data() + capacity(), data() + size(), data() + capacity()); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __annotate_increase(size_type __n) const _NOEXCEPT { __annotate_contiguous_container(data(), data() + capacity(), data() + size(), data() + size() + __n); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __annotate_shrink(size_type __old_size) const _NOEXCEPT { __annotate_contiguous_container(data(), data() + capacity(), data() + __old_size, data() + size()); } struct _ConstructTransaction { _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit _ConstructTransaction(vector &__v, size_type __n) : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) { #ifndef _LIBCPP_HAS_NO_ASAN __v_.__annotate_increase(__n); #endif } _LIBCPP_CONSTEXPR_AFTER_CXX17 ~_ConstructTransaction() { __v_.__end_ = __pos_; #ifndef _LIBCPP_HAS_NO_ASAN if (__pos_ != __new_end_) { __v_.__annotate_shrink(__new_end_ - __v_.__begin_); } #endif } vector &__v_; pointer __pos_; const_pointer const __new_end_; private: _ConstructTransaction(_ConstructTransaction const&) = delete; _ConstructTransaction& operator=(_ConstructTransaction const&) = delete; }; template _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __construct_one_at_end(_Args&& ...__args) { _ConstructTransaction __tx(*this, 1); __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_), _VSTD::forward<_Args>(__args)...); ++__tx.__pos_; } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() _NOEXCEPT {return this->__end_cap_.second();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const allocator_type& __alloc() const _NOEXCEPT {return this->__end_cap_.second();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return this->__end_cap_.first();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return this->__end_cap_.first();} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __clear() _NOEXCEPT {__base_destruct_at_end(this->__begin_);} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __base_destruct_at_end(pointer __new_last) _NOEXCEPT { pointer __soon_to_be_end = this->__end_; while (__new_last != __soon_to_be_end) __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__soon_to_be_end)); this->__end_ = __new_last; } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const vector& __c) {__copy_assign_alloc(__c, integral_constant());} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(vector& __c) _NOEXCEPT_( !__alloc_traits::propagate_on_container_move_assignment::value || is_nothrow_move_assignable::value) {__move_assign_alloc(__c, integral_constant());} _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { _VSTD::__throw_length_error("vector"); } _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { _VSTD::__throw_out_of_range("vector"); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const vector& __c, true_type) { if (__alloc() != __c.__alloc()) { __clear(); __alloc_traits::deallocate(__alloc(), this->__begin_, capacity()); this->__begin_ = this->__end_ = __end_cap() = nullptr; } __alloc() = __c.__alloc(); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const vector&, false_type) {} _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value) { __alloc() = _VSTD::move(__c.__alloc()); } _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(vector&, false_type) _NOEXCEPT {} }; #if _LIBCPP_STD_VER >= 17 template>, class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, class = enable_if_t<__is_allocator<_Alloc>::value> > vector(_InputIterator, _InputIterator) -> vector<__iter_value_type<_InputIterator>, _Alloc>; template::value>, class = enable_if_t<__is_allocator<_Alloc>::value> > vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iter_value_type<_InputIterator>, _Alloc>; #endif template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer& __v) { __annotate_delete(); using _RevIter = std::reverse_iterator; __v.__begin_ = std::__uninitialized_allocator_move_if_noexcept( __alloc(), _RevIter(__end_), _RevIter(__begin_), _RevIter(__v.__begin_)) .base(); _VSTD::swap(this->__begin_, __v.__begin_); _VSTD::swap(this->__end_, __v.__end_); _VSTD::swap(this->__end_cap(), __v.__end_cap()); __v.__first_ = __v.__begin_; __annotate_new(size()); std::__debug_db_invalidate_all(this); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::pointer vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer& __v, pointer __p) { __annotate_delete(); pointer __r = __v.__begin_; using _RevIter = std::reverse_iterator; __v.__begin_ = std::__uninitialized_allocator_move_if_noexcept( __alloc(), _RevIter(__p), _RevIter(__begin_), _RevIter(__v.__begin_)) .base(); __v.__end_ = std::__uninitialized_allocator_move_if_noexcept(__alloc(), __p, __end_, __v.__end_); _VSTD::swap(this->__begin_, __v.__begin_); _VSTD::swap(this->__end_, __v.__end_); _VSTD::swap(this->__end_cap(), __v.__end_cap()); __v.__first_ = __v.__begin_; __annotate_new(size()); std::__debug_db_invalidate_all(this); return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT { if (this->__begin_ != nullptr) { clear(); __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); this->__begin_ = this->__end_ = this->__end_cap() = nullptr; } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::size_type vector<_Tp, _Allocator>::max_size() const _NOEXCEPT { return _VSTD::min(__alloc_traits::max_size(this->__alloc()), numeric_limits::max()); } // Precondition: __new_size > capacity() template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type vector<_Tp, _Allocator>::__recommend(size_type __new_size) const { const size_type __ms = max_size(); if (__new_size > __ms) this->__throw_length_error(); const size_type __cap = capacity(); if (__cap >= __ms / 2) return __ms; return _VSTD::max(2 * __cap, __new_size); } // Default constructs __n objects starting at __end_ // throws if construction throws // Precondition: __n > 0 // Precondition: size() + __n <= capacity() // Postcondition: size() == size() + __n template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) { _ConstructTransaction __tx(*this, __n); const_pointer __new_end = __tx.__new_end_; for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) { __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos)); } } // Copy constructs __n objects starting at __end_ from __x // throws if construction throws // Precondition: __n > 0 // Precondition: size() + __n <= capacity() // Postcondition: size() == old size() + __n // Postcondition: [i] == __x for all i in [size() - __n, __n) template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline void vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) { _ConstructTransaction __tx(*this, __n); const_pointer __new_end = __tx.__new_end_; for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) { __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), __x); } } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n) { _ConstructTransaction __tx(*this, __n); __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_); } // Default constructs __n objects starting at __end_ // throws if construction throws // Postcondition: size() == size() + __n // Exception safety: strong. template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__append(size_type __n) { if (static_cast(this->__end_cap() - this->__end_) >= __n) this->__construct_at_end(__n); else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + __n), size(), __a); __v.__construct_at_end(__n); __swap_out_circular_buffer(__v); } } // Default constructs __n objects starting at __end_ // throws if construction throws // Postcondition: size() == size() + __n // Exception safety: strong. template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) { if (static_cast(this->__end_cap() - this->__end_) >= __n) this->__construct_at_end(__n, __x); else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + __n), size(), __a); __v.__construct_at_end(__n, __x); __swap_out_circular_buffer(__v); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(size_type __n) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); if (__n > 0) { __vallocate(__n); __construct_at_end(__n); } + __guard.__complete(); } #if _LIBCPP_STD_VER > 11 template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a) : __end_cap_(nullptr, __a) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); if (__n > 0) { __vallocate(__n); __construct_at_end(__n); } + __guard.__complete(); } #endif template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); if (__n > 0) { __vallocate(__n); __construct_at_end(__n, __x); } + __guard.__complete(); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(_InputIterator __first, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value, _InputIterator>::type __last) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); for (; __first != __last; ++__first) emplace_back(*__first); + __guard.__complete(); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value>::type*) : __end_cap_(nullptr, __a) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); for (; __first != __last; ++__first) emplace_back(*__first); + __guard.__complete(); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value, _ForwardIterator>::type __last) { - _VSTD::__debug_db_insert_c(this); - size_type __n = static_cast(_VSTD::distance(__first, __last)); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); + size_type __n = static_cast(std::distance(__first, __last)); if (__n > 0) { __vallocate(__n); __construct_at_end(__first, __last, __n); } + __guard.__complete(); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value>::type*) : __end_cap_(nullptr, __a) { - _VSTD::__debug_db_insert_c(this); - size_type __n = static_cast(_VSTD::distance(__first, __last)); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); + size_type __n = static_cast(std::distance(__first, __last)); if (__n > 0) { __vallocate(__n); __construct_at_end(__first, __last, __n); } + __guard.__complete(); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(const vector& __x) : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc())) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); size_type __n = __x.size(); if (__n > 0) { __vallocate(__n); __construct_at_end(__x.__begin_, __x.__end_, __n); } + __guard.__complete(); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t& __a) : __end_cap_(nullptr, __a) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); size_type __n = __x.size(); if (__n > 0) { __vallocate(__n); __construct_at_end(__x.__begin_, __x.__end_, __n); } + __guard.__complete(); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>::vector(vector&& __x) #if _LIBCPP_STD_VER > 14 noexcept #else _NOEXCEPT_(is_nothrow_move_constructible::value) #endif : __end_cap_(nullptr, _VSTD::move(__x.__alloc())) { _VSTD::__debug_db_insert_c(this); std::__debug_db_swap(this, std::addressof(__x)); this->__begin_ = __x.__begin_; this->__end_ = __x.__end_; this->__end_cap() = __x.__end_cap(); __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t& __a) : __end_cap_(nullptr, __a) { _VSTD::__debug_db_insert_c(this); if (__a == __x.__alloc()) { this->__begin_ = __x.__begin_; this->__end_ = __x.__end_; this->__end_cap() = __x.__end_cap(); __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; std::__debug_db_swap(this, std::addressof(__x)); } else { typedef move_iterator _Ip; + auto __guard = std::__make_transaction(__destroy_vector(*this)); assign(_Ip(__x.begin()), _Ip(__x.end())); + __guard.__complete(); } } #ifndef _LIBCPP_CXX03_LANG template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>::vector(initializer_list __il) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); if (__il.size() > 0) { __vallocate(__il.size()); __construct_at_end(__il.begin(), __il.end(), __il.size()); } + __guard.__complete(); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>::vector(initializer_list __il, const allocator_type& __a) : __end_cap_(nullptr, __a) { - _VSTD::__debug_db_insert_c(this); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + std::__debug_db_insert_c(this); if (__il.size() > 0) { __vallocate(__il.size()); __construct_at_end(__il.begin(), __il.end(), __il.size()); } + __guard.__complete(); } #endif // _LIBCPP_CXX03_LANG template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>& vector<_Tp, _Allocator>::operator=(vector&& __x) _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) { __move_assign(__x, integral_constant()); return *this; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) _NOEXCEPT_(__alloc_traits::is_always_equal::value) { if (__alloc() != __c.__alloc()) { typedef move_iterator _Ip; assign(_Ip(__c.begin()), _Ip(__c.end())); } else __move_assign(__c, true_type()); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value) { __vdeallocate(); __move_assign_alloc(__c); // this can throw this->__begin_ = __c.__begin_; this->__end_ = __c.__end_; this->__end_cap() = __c.__end_cap(); __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; std::__debug_db_swap(this, std::addressof(__c)); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY vector<_Tp, _Allocator>& vector<_Tp, _Allocator>::operator=(const vector& __x) { if (this != _VSTD::addressof(__x)) { __copy_assign_alloc(__x); assign(__x.__begin_, __x.__end_); } return *this; } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< _Tp, typename iterator_traits<_InputIterator>::reference>::value, void >::type vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { clear(); for (; __first != __last; ++__first) emplace_back(*__first); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< _Tp, typename iterator_traits<_ForwardIterator>::reference>::value, void >::type vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { size_type __new_size = static_cast(_VSTD::distance(__first, __last)); if (__new_size <= capacity()) { _ForwardIterator __mid = __last; bool __growing = false; if (__new_size > size()) { __growing = true; __mid = __first; _VSTD::advance(__mid, size()); } pointer __m = _VSTD::copy(__first, __mid, this->__begin_); if (__growing) __construct_at_end(__mid, __last, __new_size - size()); else this->__destruct_at_end(__m); } else { __vdeallocate(); __vallocate(__recommend(__new_size)); __construct_at_end(__first, __last, __new_size); } std::__debug_db_invalidate_all(this); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) { if (__n <= capacity()) { size_type __s = size(); _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); if (__n > __s) __construct_at_end(__n - __s, __u); else this->__destruct_at_end(this->__begin_ + __n); } else { __vdeallocate(); __vallocate(__recommend(static_cast(__n))); __construct_at_end(__n, __u); } std::__debug_db_invalidate_all(this); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::begin() _NOEXCEPT { return iterator(this, this->__begin_); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::const_iterator vector<_Tp, _Allocator>::begin() const _NOEXCEPT { return const_iterator(this, this->__begin_); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::end() _NOEXCEPT { return iterator(this, this->__end_); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::const_iterator vector<_Tp, _Allocator>::end() const _NOEXCEPT { return const_iterator(this, this->__end_); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::reference vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT { _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); return this->__begin_[__n]; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::const_reference vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT { _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); return this->__begin_[__n]; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::reference vector<_Tp, _Allocator>::at(size_type __n) { if (__n >= size()) this->__throw_out_of_range(); return this->__begin_[__n]; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::const_reference vector<_Tp, _Allocator>::at(size_type __n) const { if (__n >= size()) this->__throw_out_of_range(); return this->__begin_[__n]; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::reserve(size_type __n) { if (__n > capacity()) { if (__n > max_size()) this->__throw_length_error(); allocator_type& __a = this->__alloc(); __split_buffer __v(__n, size(), __a); __swap_out_circular_buffer(__v); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT { if (capacity() > size()) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS allocator_type& __a = this->__alloc(); __split_buffer __v(size(), size(), __a); __swap_out_circular_buffer(__v); #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { } #endif // _LIBCPP_NO_EXCEPTIONS } } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + 1), size(), __a); // __v.push_back(_VSTD::forward<_Up>(__x)); __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x)); __v.__end_++; __swap_out_circular_buffer(__v); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY void vector<_Tp, _Allocator>::push_back(const_reference __x) { if (this->__end_ != this->__end_cap()) { __construct_one_at_end(__x); } else __push_back_slow_path(__x); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY void vector<_Tp, _Allocator>::push_back(value_type&& __x) { if (this->__end_ < this->__end_cap()) { __construct_one_at_end(_VSTD::move(__x)); } else __push_back_slow_path(_VSTD::move(__x)); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + 1), size(), __a); // __v.emplace_back(_VSTD::forward<_Args>(__args)...); __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...); __v.__end_++; __swap_out_circular_buffer(__v); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline #if _LIBCPP_STD_VER > 14 typename vector<_Tp, _Allocator>::reference #else void #endif vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) { if (this->__end_ < this->__end_cap()) { __construct_one_at_end(_VSTD::forward<_Args>(__args)...); } else __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); #if _LIBCPP_STD_VER > 14 return this->back(); #endif } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline void vector<_Tp, _Allocator>::pop_back() { _LIBCPP_ASSERT(!empty(), "vector::pop_back called on an empty vector"); this->__destruct_at_end(this->__end_ - 1); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::erase(const_iterator __position) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::erase(iterator) called with an iterator not referring to this vector"); _LIBCPP_ASSERT(__position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator"); difference_type __ps = __position - cbegin(); pointer __p = this->__begin_ + __ps; this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); if (!__libcpp_is_constant_evaluated()) this->__invalidate_iterators_past(__p - 1); iterator __r = iterator(this, __p); return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this, "vector::erase(iterator, iterator) called with an iterator not referring to this vector"); _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this, "vector::erase(iterator, iterator) called with an iterator not referring to this vector"); _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); pointer __p = this->__begin_ + (__first - begin()); if (__first != __last) { this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); if (!__libcpp_is_constant_evaluated()) this->__invalidate_iterators_past(__p - 1); } iterator __r = iterator(this, __p); return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) { pointer __old_last = this->__end_; difference_type __n = __old_last - __to; { pointer __i = __from_s + __n; _ConstructTransaction __tx(*this, __from_e - __i); for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void) ++__pos, __tx.__pos_ = __pos) { __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), _VSTD::move(*__i)); } } _VSTD::move_backward(__from_s, __from_s + __n, __old_last); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::insert(iterator, x) called with an iterator not referring to this vector"); pointer __p = this->__begin_ + (__position - begin()); // We can't compare unrelated pointers inside constant expressions if (!__libcpp_is_constant_evaluated() && this->__end_ < this->__end_cap()) { if (__p == this->__end_) { __construct_one_at_end(__x); } else { __move_range(__p, this->__end_, __p + 1); const_pointer __xr = pointer_traits::pointer_to(__x); if (__p <= __xr && __xr < this->__end_) ++__xr; *__p = *__xr; } } else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + 1), __p - this->__begin_, __a); __v.push_back(__x); __p = __swap_out_circular_buffer(__v, __p); } return iterator(this, __p); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::insert(iterator, x) called with an iterator not referring to this vector"); pointer __p = this->__begin_ + (__position - begin()); if (this->__end_ < this->__end_cap()) { if (__p == this->__end_) { __construct_one_at_end(_VSTD::move(__x)); } else { __move_range(__p, this->__end_, __p + 1); *__p = _VSTD::move(__x); } } else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + 1), __p - this->__begin_, __a); __v.push_back(_VSTD::move(__x)); __p = __swap_out_circular_buffer(__v, __p); } return iterator(this, __p); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::emplace(iterator, x) called with an iterator not referring to this vector"); pointer __p = this->__begin_ + (__position - begin()); if (this->__end_ < this->__end_cap()) { if (__p == this->__end_) { __construct_one_at_end(_VSTD::forward<_Args>(__args)...); } else { __temp_value __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); __move_range(__p, this->__end_, __p + 1); *__p = _VSTD::move(__tmp.get()); } } else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + 1), __p - this->__begin_, __a); __v.emplace_back(_VSTD::forward<_Args>(__args)...); __p = __swap_out_circular_buffer(__v, __p); } return iterator(this, __p); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::insert(iterator, n, x) called with an iterator not referring to this vector"); pointer __p = this->__begin_ + (__position - begin()); if (__n > 0) { // We can't compare unrelated pointers inside constant expressions if (!__libcpp_is_constant_evaluated() && __n <= static_cast(this->__end_cap() - this->__end_)) { size_type __old_n = __n; pointer __old_last = this->__end_; if (__n > static_cast(this->__end_ - __p)) { size_type __cx = __n - (this->__end_ - __p); __construct_at_end(__cx, __x); __n -= __cx; } if (__n > 0) { __move_range(__p, __old_last, __p + __old_n); const_pointer __xr = pointer_traits::pointer_to(__x); if (__p <= __xr && __xr < this->__end_) __xr += __old_n; _VSTD::fill_n(__p, __n, *__xr); } } else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + __n), __p - this->__begin_, __a); __v.__construct_at_end(__n, __x); __p = __swap_out_circular_buffer(__v, __p); } } return iterator(this, __p); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible< _Tp, typename iterator_traits<_InputIterator>::reference>::value, typename vector<_Tp, _Allocator>::iterator >::type vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::insert(iterator, range) called with an iterator not referring to this vector"); difference_type __off = __position - begin(); pointer __p = this->__begin_ + __off; allocator_type& __a = this->__alloc(); pointer __old_last = this->__end_; for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) { __construct_one_at_end(*__first); } __split_buffer __v(__a); if (__first != __last) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS __v.__construct_at_end(__first, __last); difference_type __old_size = __old_last - this->__begin_; difference_type __old_p = __p - this->__begin_; reserve(__recommend(size() + __v.size())); __p = this->__begin_ + __old_p; __old_last = this->__begin_ + __old_size; #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { erase(iterator(this, __old_last), end()); throw; } #endif // _LIBCPP_NO_EXCEPTIONS } __p = _VSTD::rotate(__p, __old_last, this->__end_); insert(iterator(this, __p), _VSTD::make_move_iterator(__v.begin()), _VSTD::make_move_iterator(__v.end())); return begin() + __off; } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value && is_constructible< _Tp, typename iterator_traits<_ForwardIterator>::reference>::value, typename vector<_Tp, _Allocator>::iterator >::type vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this, "vector::insert(iterator, range) called with an iterator not referring to this vector"); pointer __p = this->__begin_ + (__position - begin()); difference_type __n = _VSTD::distance(__first, __last); if (__n > 0) { if (__n <= this->__end_cap() - this->__end_) { size_type __old_n = __n; pointer __old_last = this->__end_; _ForwardIterator __m = __last; difference_type __dx = this->__end_ - __p; if (__n > __dx) { __m = __first; difference_type __diff = this->__end_ - __p; _VSTD::advance(__m, __diff); __construct_at_end(__m, __last, __n - __diff); __n = __dx; } if (__n > 0) { __move_range(__p, __old_last, __p + __old_n); _VSTD::copy(__first, __m, __p); } } else { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + __n), __p - this->__begin_, __a); __v.__construct_at_end(__first, __last); __p = __swap_out_circular_buffer(__v, __p); } } return iterator(this, __p); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::resize(size_type __sz) { size_type __cs = size(); if (__cs < __sz) this->__append(__sz - __cs); else if (__cs > __sz) this->__destruct_at_end(this->__begin_ + __sz); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) { size_type __cs = size(); if (__cs < __sz) this->__append(__sz - __cs, __x); else if (__cs > __sz) this->__destruct_at_end(this->__begin_ + __sz); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector<_Tp, _Allocator>::swap(vector& __x) #if _LIBCPP_STD_VER >= 14 _NOEXCEPT #else _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable::value) #endif { _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || this->__alloc() == __x.__alloc(), "vector::swap: Either propagate_on_container_swap must be true" " or the allocators must compare equal"); _VSTD::swap(this->__begin_, __x.__begin_); _VSTD::swap(this->__end_, __x.__end_); _VSTD::swap(this->__end_cap(), __x.__end_cap()); _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(), integral_constant()); std::__debug_db_swap(this, std::addressof(__x)); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 bool vector<_Tp, _Allocator>::__invariants() const { if (this->__begin_ == nullptr) { if (this->__end_ != nullptr || this->__end_cap() != nullptr) return false; } else { if (this->__begin_ > this->__end_) return false; if (this->__begin_ == this->__end_cap()) return false; if (this->__end_ > this->__end_cap()) return false; } return true; } #ifdef _LIBCPP_ENABLE_DEBUG_MODE template bool vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const { return this->__begin_ <= __i->base() && __i->base() < this->__end_; } template bool vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const { return this->__begin_ < __i->base() && __i->base() <= this->__end_; } template bool vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const { const_pointer __p = __i->base() + __n; return this->__begin_ <= __p && __p <= this->__end_; } template bool vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const { const_pointer __p = __i->base() + __n; return this->__begin_ <= __p && __p < this->__end_; } #endif // _LIBCPP_ENABLE_DEBUG_MODE template inline _LIBCPP_INLINE_VISIBILITY void vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) { #ifdef _LIBCPP_ENABLE_DEBUG_MODE __c_node* __c = __get_db()->__find_c_and_lock(this); for (__i_node** __p = __c->end_; __p != __c->beg_; ) { --__p; const_iterator* __i = static_cast((*__p)->__i_); if (__i->base() > __new_last) { (*__p)->__c_ = nullptr; if (--__c->end_ != __p) _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); } } __get_db()->unlock(); #else ((void)__new_last); #endif } // vector template class vector; template struct hash >; template struct __has_storage_type > { static const bool value = true; }; template class _LIBCPP_TEMPLATE_VIS vector { public: typedef vector __self; typedef bool value_type; typedef _Allocator allocator_type; typedef allocator_traits __alloc_traits; typedef typename __alloc_traits::size_type size_type; typedef typename __alloc_traits::difference_type difference_type; typedef size_type __storage_type; typedef __bit_iterator pointer; typedef __bit_iterator const_pointer; typedef pointer iterator; typedef const_pointer const_iterator; typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; private: typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator; typedef allocator_traits<__storage_allocator> __storage_traits; typedef typename __storage_traits::pointer __storage_pointer; typedef typename __storage_traits::const_pointer __const_storage_pointer; __storage_pointer __begin_; size_type __size_; __compressed_pair __cap_alloc_; public: typedef __bit_reference reference; #ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL using const_reference = bool; #else typedef __bit_const_reference const_reference; #endif private: _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type& __cap() _NOEXCEPT {return __cap_alloc_.first();} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const size_type& __cap() const _NOEXCEPT {return __cap_alloc_.first();} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 __storage_allocator& __alloc() _NOEXCEPT {return __cap_alloc_.second();} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const __storage_allocator& __alloc() const _NOEXCEPT {return __cap_alloc_.second();} static const unsigned __bits_per_word = static_cast(sizeof(__storage_type) * CHAR_BIT); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT {return __n * __bits_per_word;} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT {return (__n - 1) / __bits_per_word + 1;} public: _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector() _NOEXCEPT_(is_nothrow_default_constructible::value); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(const allocator_type& __a) #if _LIBCPP_STD_VER <= 14 _NOEXCEPT_(is_nothrow_copy_constructible::value); #else _NOEXCEPT; #endif - _LIBCPP_CONSTEXPR_AFTER_CXX17 ~vector(); - _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(size_type __n); + +private: + class __destroy_vector { + public: + _LIBCPP_CONSTEXPR __destroy_vector(vector& __vec) : __vec_(__vec) {} + + _LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI void operator()() { + if (__vec_.__begin_ != nullptr) + __storage_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.__cap()); + std::__debug_db_invalidate_all(this); + } + + private: + vector& __vec_; + }; + +public: + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 ~vector() { __destroy_vector(*this)(); } + + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(size_type __n); #if _LIBCPP_STD_VER > 11 _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit vector(size_type __n, const allocator_type& __a); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(size_type __n, const value_type& __v); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(size_type __n, const value_type& __v, const allocator_type& __a); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_InputIterator __first, _InputIterator __last, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type* = 0); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type* = 0); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_ForwardIterator __first, _ForwardIterator __last, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0); template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(const vector& __v); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(const vector& __v, const allocator_type& __a); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector& operator=(const vector& __v); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(initializer_list __il); _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(initializer_list __il, const allocator_type& __a); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector& operator=(initializer_list __il) {assign(__il.begin(), __il.end()); return *this;} #endif // !_LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(vector&& __v) #if _LIBCPP_STD_VER > 14 noexcept; #else _NOEXCEPT_(is_nothrow_move_constructible::value); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 vector(vector&& __v, const __type_identity_t& __a); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector& operator=(vector&& __v) _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); template typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value, void >::type _LIBCPP_CONSTEXPR_AFTER_CXX17 assign(_InputIterator __first, _InputIterator __last); template typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type _LIBCPP_CONSTEXPR_AFTER_CXX17 assign(_ForwardIterator __first, _ForwardIterator __last); _LIBCPP_CONSTEXPR_AFTER_CXX17 void assign(size_type __n, const value_type& __x); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void assign(initializer_list __il) {assign(__il.begin(), __il.end());} #endif _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(this->__alloc());} _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type max_size() const _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type capacity() const _NOEXCEPT {return __internal_cap_to_external(__cap());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type size() const _NOEXCEPT {return __size_;} _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool empty() const _NOEXCEPT {return __size_ == 0;} _LIBCPP_CONSTEXPR_AFTER_CXX17 void reserve(size_type __n); _LIBCPP_CONSTEXPR_AFTER_CXX17 void shrink_to_fit() _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator begin() _NOEXCEPT {return __make_iter(0);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_iterator begin() const _NOEXCEPT {return __make_iter(0);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator end() _NOEXCEPT {return __make_iter(__size_);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_iterator end() const _NOEXCEPT {return __make_iter(__size_);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reverse_iterator rbegin() const _NOEXCEPT {return const_reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reverse_iterator rend() const _NOEXCEPT {return const_reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_iterator cbegin() const _NOEXCEPT {return __make_iter(0);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_iterator cend() const _NOEXCEPT {return __make_iter(__size_);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reverse_iterator crend() const _NOEXCEPT {return rend();} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reference operator[](size_type __n) {return __make_ref(__n);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reference operator[](size_type __n) const {return __make_ref(__n);} reference at(size_type __n); const_reference at(size_type __n) const; _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reference front() {return __make_ref(0);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reference front() const {return __make_ref(0);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reference back() {return __make_ref(__size_ - 1);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reference back() const {return __make_ref(__size_ - 1);} _LIBCPP_CONSTEXPR_AFTER_CXX17 void push_back(const value_type& __x); #if _LIBCPP_STD_VER > 11 template #if _LIBCPP_STD_VER > 14 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reference emplace_back(_Args&&... __args) #else _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args) #endif { push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); #if _LIBCPP_STD_VER > 14 return this->back(); #endif } #endif _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void pop_back() {--__size_;} #if _LIBCPP_STD_VER > 11 template _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator emplace(const_iterator __position, _Args&&... __args) { return insert ( __position, value_type ( _VSTD::forward<_Args>(__args)... )); } #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, const value_type& __x); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, size_type __n, const value_type& __x); template typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value, iterator >::type _LIBCPP_CONSTEXPR_AFTER_CXX17 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); template typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, iterator >::type _LIBCPP_CONSTEXPR_AFTER_CXX17 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator insert(const_iterator __position, initializer_list __il) {return insert(__position, __il.begin(), __il.end());} #endif _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator erase(const_iterator __position); _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator erase(const_iterator __first, const_iterator __last); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void clear() _NOEXCEPT {__size_ = 0;} _LIBCPP_CONSTEXPR_AFTER_CXX17 void swap(vector&) #if _LIBCPP_STD_VER >= 14 _NOEXCEPT; #else _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable::value); #endif _LIBCPP_CONSTEXPR_AFTER_CXX17 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); } _LIBCPP_CONSTEXPR_AFTER_CXX17 void resize(size_type __sz, value_type __x = false); _LIBCPP_CONSTEXPR_AFTER_CXX17 void flip() _NOEXCEPT; _LIBCPP_CONSTEXPR_AFTER_CXX17 bool __invariants() const; private: _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { _VSTD::__throw_length_error("vector"); } _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { _VSTD::__throw_out_of_range("vector"); } // Allocate space for __n objects // throws length_error if __n > max_size() // throws (probably bad_alloc) if memory run out // Precondition: __begin_ == __end_ == __cap() == 0 // Precondition: __n > 0 // Postcondition: capacity() >= __n // Postcondition: size() == 0 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void __vallocate(size_type __n) { if (__n > max_size()) __throw_length_error(); auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n)); __begin_ = __allocation.ptr; __size_ = 0; __cap() = __allocation.count; if (__libcpp_is_constant_evaluated()) { for (size_type __i = 0; __i != __cap(); ++__i) std::__construct_at(std::__to_address(__begin_) + __i); } } _LIBCPP_CONSTEXPR_AFTER_CXX17 void __vdeallocate() _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 static size_type __align_it(size_type __new_size) _NOEXCEPT {return (__new_size + (__bits_per_word-1)) & ~((size_type)__bits_per_word-1);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_type __recommend(size_type __new_size) const; _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __construct_at_end(size_type __n, bool __x); template typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type _LIBCPP_CONSTEXPR_AFTER_CXX17 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __append(size_type __n, const_reference __x); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 reference __make_ref(size_type __pos) _NOEXCEPT {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_reference __make_ref(size_type __pos) const _NOEXCEPT { return __bit_const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); } _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator __make_iter(size_type __pos) _NOEXCEPT {return iterator(__begin_ + __pos / __bits_per_word, static_cast(__pos % __bits_per_word));} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast(__pos % __bits_per_word));} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {return begin() + (__p - cbegin());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __copy_assign_alloc(const vector& __v) {__copy_assign_alloc(__v, integral_constant());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __copy_assign_alloc(const vector& __c, true_type) { if (__alloc() != __c.__alloc()) __vdeallocate(); __alloc() = __c.__alloc(); } _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __copy_assign_alloc(const vector&, false_type) {} _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign(vector& __c, false_type); _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value); _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign_alloc(vector& __c) _NOEXCEPT_( !__storage_traits::propagate_on_container_move_assignment::value || is_nothrow_move_assignable::value) {__move_assign_alloc(__c, integral_constant());} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign_alloc(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value) { __alloc() = _VSTD::move(__c.__alloc()); } _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {} _LIBCPP_CONSTEXPR_AFTER_CXX17 size_t __hash_code() const _NOEXCEPT; friend class __bit_reference; friend class __bit_const_reference; friend class __bit_iterator; friend class __bit_iterator; friend struct __bit_array; friend struct _LIBCPP_TEMPLATE_VIS hash; }; template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::__vdeallocate() _NOEXCEPT { if (this->__begin_ != nullptr) { __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); std::__debug_db_invalidate_all(this); this->__begin_ = nullptr; this->__size_ = this->__cap() = 0; } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::size_type vector::max_size() const _NOEXCEPT { size_type __amax = __storage_traits::max_size(__alloc()); size_type __nmax = numeric_limits::max() / 2; // end() >= begin(), always if (__nmax / __bits_per_word <= __amax) return __nmax; return __internal_cap_to_external(__amax); } // Precondition: __new_size > capacity() template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::size_type vector::__recommend(size_type __new_size) const { const size_type __ms = max_size(); if (__new_size > __ms) this->__throw_length_error(); const size_type __cap = capacity(); if (__cap >= __ms / 2) return __ms; return _VSTD::max(2 * __cap, __align_it(__new_size)); } // Default constructs __n objects starting at __end_ // Precondition: __n > 0 // Precondition: size() + __n <= capacity() // Postcondition: size() == size() + __n template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::__construct_at_end(size_type __n, bool __x) { size_type __old_size = this->__size_; this->__size_ += __n; if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) { if (this->__size_ <= __bits_per_word) this->__begin_[0] = __storage_type(0); else this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); } _VSTD::fill_n(__make_iter(__old_size), __n, __x); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type vector::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) { size_type __old_size = this->__size_; this->__size_ += _VSTD::distance(__first, __last); if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) { if (this->__size_ <= __bits_per_word) this->__begin_[0] = __storage_type(0); else this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); } _VSTD::copy(__first, __last, __make_iter(__old_size)); } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector() _NOEXCEPT_(is_nothrow_default_constructible::value) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(const allocator_type& __a) #if _LIBCPP_STD_VER <= 14 _NOEXCEPT_(is_nothrow_copy_constructible::value) #else _NOEXCEPT #endif : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(size_type __n) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { if (__n > 0) { __vallocate(__n); __construct_at_end(__n, false); } } #if _LIBCPP_STD_VER > 11 template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(size_type __n, const allocator_type& __a) : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { if (__n > 0) { __vallocate(__n); __construct_at_end(__n, false); } } #endif template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(size_type __n, const value_type& __x) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { if (__n > 0) { __vallocate(__n); __construct_at_end(__n, __x); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(size_type __n, const value_type& __x, const allocator_type& __a) : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { if (__n > 0) { __vallocate(__n); __construct_at_end(__n, __x); } } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(_InputIterator __first, _InputIterator __last, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type*) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS for (; __first != __last; ++__first) push_back(*__first); #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { if (__begin_ != nullptr) __storage_traits::deallocate(__alloc(), __begin_, __cap()); std::__debug_db_invalidate_all(this); throw; } #endif // _LIBCPP_NO_EXCEPTIONS } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type*) : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS for (; __first != __last; ++__first) push_back(*__first); #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { if (__begin_ != nullptr) __storage_traits::deallocate(__alloc(), __begin_, __cap()); std::__debug_db_invalidate_all(this); throw; } #endif // _LIBCPP_NO_EXCEPTIONS } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(_ForwardIterator __first, _ForwardIterator __last, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { - size_type __n = static_cast(_VSTD::distance(__first, __last)); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + size_type __n = static_cast(std::distance(__first, __last)); if (__n > 0) { __vallocate(__n); __construct_at_end(__first, __last); } + __guard.__complete(); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*) : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { - size_type __n = static_cast(_VSTD::distance(__first, __last)); + auto __guard = std::__make_transaction(__destroy_vector(*this)); + size_type __n = static_cast(std::distance(__first, __last)); if (__n > 0) { __vallocate(__n); __construct_at_end(__first, __last); } + __guard.__complete(); } #ifndef _LIBCPP_CXX03_LANG template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(initializer_list __il) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { size_type __n = static_cast(__il.size()); if (__n > 0) { __vallocate(__n); __construct_at_end(__il.begin(), __il.end()); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(initializer_list __il, const allocator_type& __a) : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { size_type __n = static_cast(__il.size()); if (__n > 0) { __vallocate(__n); __construct_at_end(__il.begin(), __il.end()); } } #endif // _LIBCPP_CXX03_LANG -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 -vector::~vector() -{ - if (__begin_ != nullptr) - __storage_traits::deallocate(__alloc(), __begin_, __cap()); - std::__debug_db_invalidate_all(this); -} - template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(const vector& __v) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) { if (__v.size() > 0) { __vallocate(__v.size()); __construct_at_end(__v.begin(), __v.end()); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(const vector& __v, const allocator_type& __a) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) { if (__v.size() > 0) { __vallocate(__v.size()); __construct_at_end(__v.begin(), __v.end()); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector& vector::operator=(const vector& __v) { if (this != _VSTD::addressof(__v)) { __copy_assign_alloc(__v); if (__v.__size_) { if (__v.__size_ > capacity()) { __vdeallocate(); __vallocate(__v.__size_); } _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); } __size_ = __v.__size_; } return *this; } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(vector&& __v) #if _LIBCPP_STD_VER > 14 _NOEXCEPT #else _NOEXCEPT_(is_nothrow_move_constructible::value) #endif : __begin_(__v.__begin_), __size_(__v.__size_), __cap_alloc_(_VSTD::move(__v.__cap_alloc_)) { __v.__begin_ = nullptr; __v.__size_ = 0; __v.__cap() = 0; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 vector::vector(vector&& __v, const __type_identity_t& __a) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) { if (__a == allocator_type(__v.__alloc())) { this->__begin_ = __v.__begin_; this->__size_ = __v.__size_; this->__cap() = __v.__cap(); __v.__begin_ = nullptr; __v.__cap() = __v.__size_ = 0; } else if (__v.size() > 0) { __vallocate(__v.size()); __construct_at_end(__v.begin(), __v.end()); } } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 vector& vector::operator=(vector&& __v) _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) { __move_assign(__v, integral_constant()); return *this; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::__move_assign(vector& __c, false_type) { if (__alloc() != __c.__alloc()) assign(__c.begin(), __c.end()); else __move_assign(__c, true_type()); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::__move_assign(vector& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable::value) { __vdeallocate(); __move_assign_alloc(__c); this->__begin_ = __c.__begin_; this->__size_ = __c.__size_; this->__cap() = __c.__cap(); __c.__begin_ = nullptr; __c.__cap() = __c.__size_ = 0; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::assign(size_type __n, const value_type& __x) { __size_ = 0; if (__n > 0) { size_type __c = capacity(); if (__n <= __c) __size_ = __n; else { vector __v(get_allocator()); __v.reserve(__recommend(__n)); __v.__size_ = __n; swap(__v); } _VSTD::fill_n(begin(), __n, __x); } std::__debug_db_invalidate_all(this); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value, void >::type vector::assign(_InputIterator __first, _InputIterator __last) { clear(); for (; __first != __last; ++__first) push_back(*__first); } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, void >::type vector::assign(_ForwardIterator __first, _ForwardIterator __last) { clear(); difference_type __ns = _VSTD::distance(__first, __last); _LIBCPP_ASSERT(__ns >= 0, "invalid range specified"); const size_t __n = static_cast(__ns); if (__n) { if (__n > capacity()) { __vdeallocate(); __vallocate(__n); } __construct_at_end(__first, __last); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::reserve(size_type __n) { if (__n > capacity()) { if (__n > max_size()) this->__throw_length_error(); vector __v(this->get_allocator()); __v.__vallocate(__n); __v.__construct_at_end(this->begin(), this->end()); swap(__v); std::__debug_db_invalidate_all(this); } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::shrink_to_fit() _NOEXCEPT { if (__external_cap_to_internal(size()) > __cap()) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS vector(*this, allocator_type(__alloc())).swap(*this); #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { } #endif // _LIBCPP_NO_EXCEPTIONS } } template typename vector::reference vector::at(size_type __n) { if (__n >= size()) this->__throw_out_of_range(); return (*this)[__n]; } template typename vector::const_reference vector::at(size_type __n) const { if (__n >= size()) this->__throw_out_of_range(); return (*this)[__n]; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::push_back(const value_type& __x) { if (this->__size_ == this->capacity()) reserve(__recommend(this->__size_ + 1)); ++this->__size_; back() = __x; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::iterator vector::insert(const_iterator __position, const value_type& __x) { iterator __r; if (size() < capacity()) { const_iterator __old_end = end(); ++__size_; _VSTD::copy_backward(__position, __old_end, end()); __r = __const_iterator_cast(__position); } else { vector __v(get_allocator()); __v.reserve(__recommend(__size_ + 1)); __v.__size_ = __size_ + 1; __r = _VSTD::copy(cbegin(), __position, __v.begin()); _VSTD::copy_backward(__position, cend(), __v.end()); swap(__v); } *__r = __x; return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::iterator vector::insert(const_iterator __position, size_type __n, const value_type& __x) { iterator __r; size_type __c = capacity(); if (__n <= __c && size() <= __c - __n) { const_iterator __old_end = end(); __size_ += __n; _VSTD::copy_backward(__position, __old_end, end()); __r = __const_iterator_cast(__position); } else { vector __v(get_allocator()); __v.reserve(__recommend(__size_ + __n)); __v.__size_ = __size_ + __n; __r = _VSTD::copy(cbegin(), __position, __v.begin()); _VSTD::copy_backward(__position, cend(), __v.end()); swap(__v); } _VSTD::fill_n(__r, __n, __x); return __r; } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value, typename vector::iterator >::type vector::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { difference_type __off = __position - begin(); iterator __p = __const_iterator_cast(__position); iterator __old_end = end(); for (; size() != capacity() && __first != __last; ++__first) { ++this->__size_; back() = *__first; } vector __v(get_allocator()); if (__first != __last) { #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS __v.assign(__first, __last); difference_type __old_size = static_cast(__old_end - begin()); difference_type __old_p = __p - begin(); reserve(__recommend(size() + __v.size())); __p = begin() + __old_p; __old_end = begin() + __old_size; #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { erase(__old_end, end()); throw; } #endif // _LIBCPP_NO_EXCEPTIONS } __p = _VSTD::rotate(__p, __old_end, end()); insert(__p, __v.begin(), __v.end()); return begin() + __off; } template template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < __is_cpp17_forward_iterator<_ForwardIterator>::value, typename vector::iterator >::type vector::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { const difference_type __n_signed = _VSTD::distance(__first, __last); _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified"); const size_type __n = static_cast(__n_signed); iterator __r; size_type __c = capacity(); if (__n <= __c && size() <= __c - __n) { const_iterator __old_end = end(); __size_ += __n; _VSTD::copy_backward(__position, __old_end, end()); __r = __const_iterator_cast(__position); } else { vector __v(get_allocator()); __v.reserve(__recommend(__size_ + __n)); __v.__size_ = __size_ + __n; __r = _VSTD::copy(cbegin(), __position, __v.begin()); _VSTD::copy_backward(__position, cend(), __v.end()); swap(__v); } _VSTD::copy(__first, __last, __r); return __r; } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::iterator vector::erase(const_iterator __position) { iterator __r = __const_iterator_cast(__position); _VSTD::copy(__position + 1, this->cend(), __r); --__size_; return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 typename vector::iterator vector::erase(const_iterator __first, const_iterator __last) { iterator __r = __const_iterator_cast(__first); difference_type __d = __last - __first; _VSTD::copy(__last, this->cend(), __r); __size_ -= __d; return __r; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::swap(vector& __x) #if _LIBCPP_STD_VER >= 14 _NOEXCEPT #else _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable::value) #endif { _VSTD::swap(this->__begin_, __x.__begin_); _VSTD::swap(this->__size_, __x.__size_); _VSTD::swap(this->__cap(), __x.__cap()); _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(), integral_constant()); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::resize(size_type __sz, value_type __x) { size_type __cs = size(); if (__cs < __sz) { iterator __r; size_type __c = capacity(); size_type __n = __sz - __cs; if (__n <= __c && __cs <= __c - __n) { __r = end(); __size_ += __n; } else { vector __v(get_allocator()); __v.reserve(__recommend(__size_ + __n)); __v.__size_ = __size_ + __n; __r = _VSTD::copy(cbegin(), cend(), __v.begin()); swap(__v); } _VSTD::fill_n(__r, __n, __x); } else __size_ = __sz; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 void vector::flip() _NOEXCEPT { // do middle whole words size_type __n = __size_; __storage_pointer __p = __begin_; for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) *__p = ~*__p; // do last partial word if (__n > 0) { __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); __storage_type __b = *__p & __m; *__p &= ~__m; *__p |= ~__b & __m; } } template _LIBCPP_CONSTEXPR_AFTER_CXX17 bool vector::__invariants() const { if (this->__begin_ == nullptr) { if (this->__size_ != 0 || this->__cap() != 0) return false; } else { if (this->__cap() == 0) return false; if (this->__size_ > this->capacity()) return false; } return true; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 size_t vector::__hash_code() const _NOEXCEPT { size_t __h = 0; // do middle whole words size_type __n = __size_; __storage_pointer __p = __begin_; for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) __h ^= *__p; // do last partial word if (__n > 0) { const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); __h ^= *__p & __m; } return __h; } template struct _LIBCPP_TEMPLATE_VIS hash > : public __unary_function, size_t> { _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 size_t operator()(const vector& __vec) const _NOEXCEPT {return __vec.__hash_code();} }; template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { return !(__x == __y); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { return __y < __x; } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { return !(__x < __y); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY bool operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { return !(__y < __x); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY void swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { __x.swap(__y); } #if _LIBCPP_STD_VER > 17 template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type erase(vector<_Tp, _Allocator>& __c, const _Up& __v) { auto __old_size = __c.size(); __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); return __old_size - __c.size(); } template _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) { auto __old_size = __c.size(); __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); return __old_size - __c.size(); } template <> inline constexpr bool __format::__enable_insertable> = true; #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS template <> inline constexpr bool __format::__enable_insertable> = true; #endif #endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS #endif // _LIBCPP_VECTOR diff --git a/llvm/lib/CodeGen/PrologEpilogInserter.cpp b/llvm/lib/CodeGen/PrologEpilogInserter.cpp index 85d051cfdbe7..a8d40edd88d3 100644 --- a/llvm/lib/CodeGen/PrologEpilogInserter.cpp +++ b/llvm/lib/CodeGen/PrologEpilogInserter.cpp @@ -1,1470 +1,1476 @@ //===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===// // // 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 // //===----------------------------------------------------------------------===// // // This pass is responsible for finalizing the functions frame layout, saving // callee saved registers, and for emitting prolog & epilog code for the // function. // // This pass must be run after register allocation. After this pass is // executed, it is illegal to construct MO_FrameIndex operands. // //===----------------------------------------------------------------------===// #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegisterScavenging.h" #include "llvm/CodeGen/TargetFrameLowering.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetOpcodes.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/CodeGen/WinEHFuncInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/CallingConv.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Function.h" #include "llvm/IR/InlineAsm.h" #include "llvm/IR/LLVMContext.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Pass.h" #include "llvm/Support/CodeGen.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" #include #include #include #include #include #include #include using namespace llvm; #define DEBUG_TYPE "prologepilog" using MBBVector = SmallVector; STATISTIC(NumLeafFuncWithSpills, "Number of leaf functions with CSRs"); STATISTIC(NumFuncSeen, "Number of functions seen in PEI"); namespace { class PEI : public MachineFunctionPass { public: static char ID; PEI() : MachineFunctionPass(ID) { initializePEIPass(*PassRegistry::getPassRegistry()); } void getAnalysisUsage(AnalysisUsage &AU) const override; /// runOnMachineFunction - Insert prolog/epilog code and replace abstract /// frame indexes with appropriate references. bool runOnMachineFunction(MachineFunction &MF) override; private: RegScavenger *RS; // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved // stack frame indexes. unsigned MinCSFrameIndex = std::numeric_limits::max(); unsigned MaxCSFrameIndex = 0; // Save and Restore blocks of the current function. Typically there is a // single save block, unless Windows EH funclets are involved. MBBVector SaveBlocks; MBBVector RestoreBlocks; // Flag to control whether to use the register scavenger to resolve // frame index materialization registers. Set according to // TRI->requiresFrameIndexScavenging() for the current function. bool FrameIndexVirtualScavenging; // Flag to control whether the scavenger should be passed even though // FrameIndexVirtualScavenging is used. bool FrameIndexEliminationScavenging; // Emit remarks. MachineOptimizationRemarkEmitter *ORE = nullptr; void calculateCallFrameInfo(MachineFunction &MF); void calculateSaveRestoreBlocks(MachineFunction &MF); void spillCalleeSavedRegs(MachineFunction &MF); void calculateFrameObjectOffsets(MachineFunction &MF); void replaceFrameIndices(MachineFunction &MF); void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF, int &SPAdj); void insertPrologEpilogCode(MachineFunction &MF); void insertZeroCallUsedRegs(MachineFunction &MF); }; } // end anonymous namespace char PEI::ID = 0; char &llvm::PrologEpilogCodeInserterID = PEI::ID; INITIALIZE_PASS_BEGIN(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion", false, false) INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass) INITIALIZE_PASS_END(PEI, DEBUG_TYPE, "Prologue/Epilogue Insertion & Frame Finalization", false, false) MachineFunctionPass *llvm::createPrologEpilogInserterPass() { return new PEI(); } STATISTIC(NumBytesStackSpace, "Number of bytes used for stack in all functions"); void PEI::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addPreserved(); AU.addPreserved(); AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } /// StackObjSet - A set of stack object indexes using StackObjSet = SmallSetVector; using SavedDbgValuesMap = SmallDenseMap, 4>; /// Stash DBG_VALUEs that describe parameters and which are placed at the start /// of the block. Later on, after the prologue code has been emitted, the /// stashed DBG_VALUEs will be reinserted at the start of the block. static void stashEntryDbgValues(MachineBasicBlock &MBB, SavedDbgValuesMap &EntryDbgValues) { SmallVector FrameIndexValues; for (auto &MI : MBB) { if (!MI.isDebugInstr()) break; if (!MI.isDebugValue() || !MI.getDebugVariable()->isParameter()) continue; if (any_of(MI.debug_operands(), [](const MachineOperand &MO) { return MO.isFI(); })) { // We can only emit valid locations for frame indices after the frame // setup, so do not stash away them. FrameIndexValues.push_back(&MI); continue; } const DILocalVariable *Var = MI.getDebugVariable(); const DIExpression *Expr = MI.getDebugExpression(); auto Overlaps = [Var, Expr](const MachineInstr *DV) { return Var == DV->getDebugVariable() && Expr->fragmentsOverlap(DV->getDebugExpression()); }; // See if the debug value overlaps with any preceding debug value that will // not be stashed. If that is the case, then we can't stash this value, as // we would then reorder the values at reinsertion. if (llvm::none_of(FrameIndexValues, Overlaps)) EntryDbgValues[&MBB].push_back(&MI); } // Remove stashed debug values from the block. if (EntryDbgValues.count(&MBB)) for (auto *MI : EntryDbgValues[&MBB]) MI->removeFromParent(); } /// runOnMachineFunction - Insert prolog/epilog code and replace abstract /// frame indexes with appropriate references. bool PEI::runOnMachineFunction(MachineFunction &MF) { NumFuncSeen++; const Function &F = MF.getFunction(); const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr; FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(MF); ORE = &getAnalysis().getORE(); // Calculate the MaxCallFrameSize and AdjustsStack variables for the // function's frame information. Also eliminates call frame pseudo // instructions. calculateCallFrameInfo(MF); // Determine placement of CSR spill/restore code and prolog/epilog code: // place all spills in the entry block, all restores in return blocks. calculateSaveRestoreBlocks(MF); // Stash away DBG_VALUEs that should not be moved by insertion of prolog code. SavedDbgValuesMap EntryDbgValues; for (MachineBasicBlock *SaveBlock : SaveBlocks) stashEntryDbgValues(*SaveBlock, EntryDbgValues); // Handle CSR spilling and restoring, for targets that need it. if (MF.getTarget().usesPhysRegsForValues()) spillCalleeSavedRegs(MF); // Allow the target machine to make final modifications to the function // before the frame layout is finalized. TFI->processFunctionBeforeFrameFinalized(MF, RS); // Calculate actual frame offsets for all abstract stack objects... calculateFrameObjectOffsets(MF); // Add prolog and epilog code to the function. This function is required // to align the stack frame as necessary for any stack variables or // called functions. Because of this, calculateCalleeSavedRegisters() // must be called before this function in order to set the AdjustsStack // and MaxCallFrameSize variables. if (!F.hasFnAttribute(Attribute::Naked)) insertPrologEpilogCode(MF); // Reinsert stashed debug values at the start of the entry blocks. for (auto &I : EntryDbgValues) I.first->insert(I.first->begin(), I.second.begin(), I.second.end()); // Allow the target machine to make final modifications to the function // before the frame layout is finalized. TFI->processFunctionBeforeFrameIndicesReplaced(MF, RS); // Replace all MO_FrameIndex operands with physical register references // and actual offsets. // replaceFrameIndices(MF); // If register scavenging is needed, as we've enabled doing it as a // post-pass, scavenge the virtual registers that frame index elimination // inserted. if (TRI->requiresRegisterScavenging(MF) && FrameIndexVirtualScavenging) scavengeFrameVirtualRegs(MF, *RS); // Warn on stack size when we exceeds the given limit. MachineFrameInfo &MFI = MF.getFrameInfo(); uint64_t StackSize = MFI.getStackSize(); unsigned Threshold = UINT_MAX; if (MF.getFunction().hasFnAttribute("warn-stack-size")) { bool Failed = MF.getFunction() .getFnAttribute("warn-stack-size") .getValueAsString() .getAsInteger(10, Threshold); // Verifier should have caught this. assert(!Failed && "Invalid warn-stack-size fn attr value"); (void)Failed; } if (MF.getFunction().hasFnAttribute(Attribute::SafeStack)) { StackSize += MFI.getUnsafeStackSize(); } if (StackSize > Threshold) { DiagnosticInfoStackSize DiagStackSize(F, StackSize, Threshold, DS_Warning); F.getContext().diagnose(DiagStackSize); } ORE->emit([&]() { return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize", MF.getFunction().getSubprogram(), &MF.front()) << ore::NV("NumStackBytes", StackSize) << " stack bytes in function"; }); delete RS; SaveBlocks.clear(); RestoreBlocks.clear(); MFI.setSavePoint(nullptr); MFI.setRestorePoint(nullptr); return true; } /// Calculate the MaxCallFrameSize and AdjustsStack /// variables for the function's frame information and eliminate call frame /// pseudo instructions. void PEI::calculateCallFrameInfo(MachineFunction &MF) { const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); MachineFrameInfo &MFI = MF.getFrameInfo(); unsigned MaxCallFrameSize = 0; bool AdjustsStack = MFI.adjustsStack(); // Get the function call frame set-up and tear-down instruction opcode unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode(); unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); // Early exit for targets which have no call frame setup/destroy pseudo // instructions. if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u) return; std::vector FrameSDOps; for (MachineBasicBlock &BB : MF) for (MachineBasicBlock::iterator I = BB.begin(); I != BB.end(); ++I) if (TII.isFrameInstr(*I)) { unsigned Size = TII.getFrameSize(*I); if (Size > MaxCallFrameSize) MaxCallFrameSize = Size; AdjustsStack = true; FrameSDOps.push_back(I); } else if (I->isInlineAsm()) { // Some inline asm's need a stack frame, as indicated by operand 1. unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm(); if (ExtraInfo & InlineAsm::Extra_IsAlignStack) AdjustsStack = true; } assert(!MFI.isMaxCallFrameSizeComputed() || (MFI.getMaxCallFrameSize() == MaxCallFrameSize && MFI.adjustsStack() == AdjustsStack)); MFI.setAdjustsStack(AdjustsStack); MFI.setMaxCallFrameSize(MaxCallFrameSize); for (MachineBasicBlock::iterator I : FrameSDOps) { // If call frames are not being included as part of the stack frame, and // the target doesn't indicate otherwise, remove the call frame pseudos // here. The sub/add sp instruction pairs are still inserted, but we don't // need to track the SP adjustment for frame index elimination. if (TFI->canSimplifyCallFramePseudos(MF)) TFI->eliminateCallFramePseudoInstr(MF, *I->getParent(), I); } } /// Compute the sets of entry and return blocks for saving and restoring /// callee-saved registers, and placing prolog and epilog code. void PEI::calculateSaveRestoreBlocks(MachineFunction &MF) { const MachineFrameInfo &MFI = MF.getFrameInfo(); // Even when we do not change any CSR, we still want to insert the // prologue and epilogue of the function. // So set the save points for those. // Use the points found by shrink-wrapping, if any. if (MFI.getSavePoint()) { SaveBlocks.push_back(MFI.getSavePoint()); assert(MFI.getRestorePoint() && "Both restore and save must be set"); MachineBasicBlock *RestoreBlock = MFI.getRestorePoint(); // If RestoreBlock does not have any successor and is not a return block // then the end point is unreachable and we do not need to insert any // epilogue. if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock()) RestoreBlocks.push_back(RestoreBlock); return; } // Save refs to entry and return blocks. SaveBlocks.push_back(&MF.front()); for (MachineBasicBlock &MBB : MF) { if (MBB.isEHFuncletEntry()) SaveBlocks.push_back(&MBB); if (MBB.isReturnBlock()) RestoreBlocks.push_back(&MBB); } } static void assignCalleeSavedSpillSlots(MachineFunction &F, const BitVector &SavedRegs, unsigned &MinCSFrameIndex, unsigned &MaxCSFrameIndex) { if (SavedRegs.empty()) return; const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo(); const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs(); BitVector CSMask(SavedRegs.size()); for (unsigned i = 0; CSRegs[i]; ++i) CSMask.set(CSRegs[i]); std::vector CSI; for (unsigned i = 0; CSRegs[i]; ++i) { unsigned Reg = CSRegs[i]; if (SavedRegs.test(Reg)) { bool SavedSuper = false; for (const MCPhysReg &SuperReg : RegInfo->superregs(Reg)) { // Some backends set all aliases for some registers as saved, such as // Mips's $fp, so they appear in SavedRegs but not CSRegs. if (SavedRegs.test(SuperReg) && CSMask.test(SuperReg)) { SavedSuper = true; break; } } if (!SavedSuper) CSI.push_back(CalleeSavedInfo(Reg)); } } const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering(); MachineFrameInfo &MFI = F.getFrameInfo(); if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI, MinCSFrameIndex, MaxCSFrameIndex)) { // If target doesn't implement this, use generic code. if (CSI.empty()) return; // Early exit if no callee saved registers are modified! unsigned NumFixedSpillSlots; const TargetFrameLowering::SpillSlot *FixedSpillSlots = TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots); // Now that we know which registers need to be saved and restored, allocate // stack slots for them. for (auto &CS : CSI) { // If the target has spilled this register to another register, we don't // need to allocate a stack slot. if (CS.isSpilledToReg()) continue; unsigned Reg = CS.getReg(); const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg); int FrameIdx; if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) { CS.setFrameIdx(FrameIdx); continue; } // Check to see if this physreg must be spilled to a particular stack slot // on this target. const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots; while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots && FixedSlot->Reg != Reg) ++FixedSlot; unsigned Size = RegInfo->getSpillSize(*RC); if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) { // Nope, just spill it anywhere convenient. Align Alignment = RegInfo->getSpillAlign(*RC); // We may not be able to satisfy the desired alignment specification of // the TargetRegisterClass if the stack alignment is smaller. Use the // min. Alignment = std::min(Alignment, TFI->getStackAlign()); FrameIdx = MFI.CreateStackObject(Size, Alignment, true); if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx; if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx; } else { // Spill it to the stack where we must. FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset); } CS.setFrameIdx(FrameIdx); } } MFI.setCalleeSavedInfo(CSI); } /// Helper function to update the liveness information for the callee-saved /// registers. static void updateLiveness(MachineFunction &MF) { MachineFrameInfo &MFI = MF.getFrameInfo(); // Visited will contain all the basic blocks that are in the region // where the callee saved registers are alive: // - Anything that is not Save or Restore -> LiveThrough. // - Save -> LiveIn. // - Restore -> LiveOut. // The live-out is not attached to the block, so no need to keep // Restore in this set. SmallPtrSet Visited; SmallVector WorkList; MachineBasicBlock *Entry = &MF.front(); MachineBasicBlock *Save = MFI.getSavePoint(); if (!Save) Save = Entry; if (Entry != Save) { WorkList.push_back(Entry); Visited.insert(Entry); } Visited.insert(Save); MachineBasicBlock *Restore = MFI.getRestorePoint(); if (Restore) // By construction Restore cannot be visited, otherwise it // means there exists a path to Restore that does not go // through Save. WorkList.push_back(Restore); while (!WorkList.empty()) { const MachineBasicBlock *CurBB = WorkList.pop_back_val(); // By construction, the region that is after the save point is // dominated by the Save and post-dominated by the Restore. if (CurBB == Save && Save != Restore) continue; // Enqueue all the successors not already visited. // Those are by construction either before Save or after Restore. for (MachineBasicBlock *SuccBB : CurBB->successors()) if (Visited.insert(SuccBB).second) WorkList.push_back(SuccBB); } const std::vector &CSI = MFI.getCalleeSavedInfo(); MachineRegisterInfo &MRI = MF.getRegInfo(); for (const CalleeSavedInfo &I : CSI) { for (MachineBasicBlock *MBB : Visited) { MCPhysReg Reg = I.getReg(); // Add the callee-saved register as live-in. // It's killed at the spill. if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg)) MBB->addLiveIn(Reg); } // If callee-saved register is spilled to another register rather than // spilling to stack, the destination register has to be marked as live for // each MBB between the prologue and epilogue so that it is not clobbered // before it is reloaded in the epilogue. The Visited set contains all // blocks outside of the region delimited by prologue/epilogue. if (I.isSpilledToReg()) { for (MachineBasicBlock &MBB : MF) { if (Visited.count(&MBB)) continue; MCPhysReg DstReg = I.getDstReg(); if (!MBB.isLiveIn(DstReg)) MBB.addLiveIn(DstReg); } } } } /// Insert spill code for the callee-saved registers used in the function. static void insertCSRSaves(MachineBasicBlock &SaveBlock, ArrayRef CSI) { MachineFunction &MF = *SaveBlock.getParent(); const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); MachineBasicBlock::iterator I = SaveBlock.begin(); if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) { for (const CalleeSavedInfo &CS : CSI) { // Insert the spill to the stack frame. unsigned Reg = CS.getReg(); if (CS.isSpilledToReg()) { BuildMI(SaveBlock, I, DebugLoc(), TII.get(TargetOpcode::COPY), CS.getDstReg()) .addReg(Reg, getKillRegState(true)); } else { const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); TII.storeRegToStackSlot(SaveBlock, I, Reg, true, CS.getFrameIdx(), RC, TRI); } } } } /// Insert restore code for the callee-saved registers used in the function. static void insertCSRRestores(MachineBasicBlock &RestoreBlock, std::vector &CSI) { MachineFunction &MF = *RestoreBlock.getParent(); const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); // Restore all registers immediately before the return and any // terminators that precede it. MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator(); if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) { for (const CalleeSavedInfo &CI : reverse(CSI)) { unsigned Reg = CI.getReg(); if (CI.isSpilledToReg()) { BuildMI(RestoreBlock, I, DebugLoc(), TII.get(TargetOpcode::COPY), Reg) .addReg(CI.getDstReg(), getKillRegState(true)); } else { const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); TII.loadRegFromStackSlot(RestoreBlock, I, Reg, CI.getFrameIdx(), RC, TRI); assert(I != RestoreBlock.begin() && "loadRegFromStackSlot didn't insert any code!"); // Insert in reverse order. loadRegFromStackSlot can insert // multiple instructions. } } } } void PEI::spillCalleeSavedRegs(MachineFunction &MF) { // We can't list this requirement in getRequiredProperties because some // targets (WebAssembly) use virtual registers past this point, and the pass // pipeline is set up without giving the passes a chance to look at the // TargetMachine. // FIXME: Find a way to express this in getRequiredProperties. assert(MF.getProperties().hasProperty( MachineFunctionProperties::Property::NoVRegs)); const Function &F = MF.getFunction(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); MachineFrameInfo &MFI = MF.getFrameInfo(); MinCSFrameIndex = std::numeric_limits::max(); MaxCSFrameIndex = 0; // Determine which of the registers in the callee save list should be saved. BitVector SavedRegs; TFI->determineCalleeSaves(MF, SavedRegs, RS); // Assign stack slots for any callee-saved registers that must be spilled. assignCalleeSavedSpillSlots(MF, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex); // Add the code to save and restore the callee saved registers. if (!F.hasFnAttribute(Attribute::Naked)) { MFI.setCalleeSavedInfoValid(true); std::vector &CSI = MFI.getCalleeSavedInfo(); if (!CSI.empty()) { if (!MFI.hasCalls()) NumLeafFuncWithSpills++; for (MachineBasicBlock *SaveBlock : SaveBlocks) insertCSRSaves(*SaveBlock, CSI); // Update the live-in information of all the blocks up to the save point. updateLiveness(MF); for (MachineBasicBlock *RestoreBlock : RestoreBlocks) insertCSRRestores(*RestoreBlock, CSI); } } } /// AdjustStackOffset - Helper function used to adjust the stack frame offset. static inline void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, bool StackGrowsDown, int64_t &Offset, Align &MaxAlign, unsigned Skew) { // If the stack grows down, add the object size to find the lowest address. if (StackGrowsDown) Offset += MFI.getObjectSize(FrameIdx); Align Alignment = MFI.getObjectAlign(FrameIdx); // If the alignment of this object is greater than that of the stack, then // increase the stack alignment to match. MaxAlign = std::max(MaxAlign, Alignment); // Adjust to alignment boundary. Offset = alignTo(Offset, Alignment, Skew); if (StackGrowsDown) { LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n"); MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset } else { LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n"); MFI.setObjectOffset(FrameIdx, Offset); Offset += MFI.getObjectSize(FrameIdx); } } /// Compute which bytes of fixed and callee-save stack area are unused and keep /// track of them in StackBytesFree. static inline void computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown, unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex, int64_t FixedCSEnd, BitVector &StackBytesFree) { // Avoid undefined int64_t -> int conversion below in extreme case. if (FixedCSEnd > std::numeric_limits::max()) return; StackBytesFree.resize(FixedCSEnd, true); SmallVector AllocatedFrameSlots; // Add fixed objects. for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) // StackSlot scavenging is only implemented for the default stack. if (MFI.getStackID(i) == TargetStackID::Default) AllocatedFrameSlots.push_back(i); // Add callee-save objects if there are any. if (MinCSFrameIndex <= MaxCSFrameIndex) { for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i) if (MFI.getStackID(i) == TargetStackID::Default) AllocatedFrameSlots.push_back(i); } for (int i : AllocatedFrameSlots) { // These are converted from int64_t, but they should always fit in int // because of the FixedCSEnd check above. int ObjOffset = MFI.getObjectOffset(i); int ObjSize = MFI.getObjectSize(i); int ObjStart, ObjEnd; if (StackGrowsDown) { // ObjOffset is negative when StackGrowsDown is true. ObjStart = -ObjOffset - ObjSize; ObjEnd = -ObjOffset; } else { ObjStart = ObjOffset; ObjEnd = ObjOffset + ObjSize; } // Ignore fixed holes that are in the previous stack frame. if (ObjEnd > 0) StackBytesFree.reset(ObjStart, ObjEnd); } } /// Assign frame object to an unused portion of the stack in the fixed stack /// object range. Return true if the allocation was successful. static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx, bool StackGrowsDown, Align MaxAlign, BitVector &StackBytesFree) { if (MFI.isVariableSizedObjectIndex(FrameIdx)) return false; if (StackBytesFree.none()) { // clear it to speed up later scavengeStackSlot calls to // StackBytesFree.none() StackBytesFree.clear(); return false; } Align ObjAlign = MFI.getObjectAlign(FrameIdx); if (ObjAlign > MaxAlign) return false; int64_t ObjSize = MFI.getObjectSize(FrameIdx); int FreeStart; for (FreeStart = StackBytesFree.find_first(); FreeStart != -1; FreeStart = StackBytesFree.find_next(FreeStart)) { // Check that free space has suitable alignment. unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart; if (alignTo(ObjStart, ObjAlign) != ObjStart) continue; if (FreeStart + ObjSize > StackBytesFree.size()) return false; bool AllBytesFree = true; for (unsigned Byte = 0; Byte < ObjSize; ++Byte) if (!StackBytesFree.test(FreeStart + Byte)) { AllBytesFree = false; break; } if (AllBytesFree) break; } if (FreeStart == -1) return false; if (StackGrowsDown) { int ObjStart = -(FreeStart + ObjSize); LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << ObjStart << "]\n"); MFI.setObjectOffset(FrameIdx, ObjStart); } else { LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP[" << FreeStart << "]\n"); MFI.setObjectOffset(FrameIdx, FreeStart); } StackBytesFree.reset(FreeStart, FreeStart + ObjSize); return true; } /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e., /// those required to be close to the Stack Protector) to stack offsets. static void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, SmallSet &ProtectedObjs, MachineFrameInfo &MFI, bool StackGrowsDown, int64_t &Offset, Align &MaxAlign, unsigned Skew) { for (int i : UnassignedObjs) { AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign, Skew); ProtectedObjs.insert(i); } } /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the /// abstract stack objects. void PEI::calculateFrameObjectOffsets(MachineFunction &MF) { const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering(); bool StackGrowsDown = TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; // Loop over all of the stack objects, assigning sequential addresses... MachineFrameInfo &MFI = MF.getFrameInfo(); // Start at the beginning of the local area. // The Offset is the distance from the stack top in the direction // of stack growth -- so it's always nonnegative. int LocalAreaOffset = TFI.getOffsetOfLocalArea(); if (StackGrowsDown) LocalAreaOffset = -LocalAreaOffset; assert(LocalAreaOffset >= 0 && "Local area offset should be in direction of stack growth"); int64_t Offset = LocalAreaOffset; // Skew to be applied to alignment. unsigned Skew = TFI.getStackAlignmentSkew(MF); #ifdef EXPENSIVE_CHECKS for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) if (!MFI.isDeadObjectIndex(i) && MFI.getStackID(i) == TargetStackID::Default) assert(MFI.getObjectAlign(i) <= MFI.getMaxAlign() && "MaxAlignment is invalid"); #endif // If there are fixed sized objects that are preallocated in the local area, // non-fixed objects can't be allocated right at the start of local area. // Adjust 'Offset' to point to the end of last fixed sized preallocated // object. for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) { // Only allocate objects on the default stack. if (MFI.getStackID(i) != TargetStackID::Default) continue; int64_t FixedOff; if (StackGrowsDown) { // The maximum distance from the stack pointer is at lower address of // the object -- which is given by offset. For down growing stack // the offset is negative, so we negate the offset to get the distance. FixedOff = -MFI.getObjectOffset(i); } else { // The maximum distance from the start pointer is at the upper // address of the object. FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i); } if (FixedOff > Offset) Offset = FixedOff; } Align MaxAlign = MFI.getMaxAlign(); // First assign frame offsets to stack objects that are used to spill // callee saved registers. if (MaxCSFrameIndex >= MinCSFrameIndex) { for (unsigned i = 0; i <= MaxCSFrameIndex - MinCSFrameIndex; ++i) { unsigned FrameIndex = StackGrowsDown ? MinCSFrameIndex + i : MaxCSFrameIndex - i; // Only allocate objects on the default stack. if (MFI.getStackID(FrameIndex) != TargetStackID::Default) continue; // TODO: should this just be if (MFI.isDeadObjectIndex(FrameIndex)) if (!StackGrowsDown && MFI.isDeadObjectIndex(FrameIndex)) continue; AdjustStackOffset(MFI, FrameIndex, StackGrowsDown, Offset, MaxAlign, Skew); } } assert(MaxAlign == MFI.getMaxAlign() && "MFI.getMaxAlign should already account for all callee-saved " "registers without a fixed stack slot"); // FixedCSEnd is the stack offset to the end of the fixed and callee-save // stack area. int64_t FixedCSEnd = Offset; // Make sure the special register scavenging spill slot is closest to the // incoming stack pointer if a frame pointer is required and is closer // to the incoming rather than the final stack pointer. const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo(); bool EarlyScavengingSlots = TFI.allocateScavengingFrameIndexesNearIncomingSP(MF); if (RS && EarlyScavengingSlots) { SmallVector SFIs; RS->getScavengingFrameIndices(SFIs); for (int SFI : SFIs) AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign, Skew); } // FIXME: Once this is working, then enable flag will change to a target // check for whether the frame is large enough to want to use virtual // frame index registers. Functions which don't want/need this optimization // will continue to use the existing code path. if (MFI.getUseLocalStackAllocationBlock()) { Align Alignment = MFI.getLocalFrameMaxAlign(); // Adjust to alignment boundary. Offset = alignTo(Offset, Alignment, Skew); LLVM_DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n"); // Resolve offsets for objects in the local block. for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) { std::pair Entry = MFI.getLocalFrameObjectMap(i); int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second; LLVM_DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << FIOffset << "]\n"); MFI.setObjectOffset(Entry.first, FIOffset); } // Allocate the local block Offset += MFI.getLocalFrameSize(); MaxAlign = std::max(Alignment, MaxAlign); } // Retrieve the Exception Handler registration node. int EHRegNodeFrameIndex = std::numeric_limits::max(); if (const WinEHFuncInfo *FuncInfo = MF.getWinEHFuncInfo()) EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex; // Make sure that the stack protector comes before the local variables on the // stack. SmallSet ProtectedObjs; if (MFI.hasStackProtectorIndex()) { int StackProtectorFI = MFI.getStackProtectorIndex(); StackObjSet LargeArrayObjs; StackObjSet SmallArrayObjs; StackObjSet AddrOfObjs; // If we need a stack protector, we need to make sure that // LocalStackSlotPass didn't already allocate a slot for it. // If we are told to use the LocalStackAllocationBlock, the stack protector // is expected to be already pre-allocated. if (MFI.getStackID(StackProtectorFI) != TargetStackID::Default) { // If the stack protector isn't on the default stack then it's up to the // target to set the stack offset. assert(MFI.getObjectOffset(StackProtectorFI) != 0 && "Offset of stack protector on non-default stack expected to be " "already set."); assert(!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex()) && "Stack protector on non-default stack expected to not be " "pre-allocated by LocalStackSlotPass."); } else if (!MFI.getUseLocalStackAllocationBlock()) { AdjustStackOffset(MFI, StackProtectorFI, StackGrowsDown, Offset, MaxAlign, Skew); } else if (!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex())) { llvm_unreachable( "Stack protector not pre-allocated by LocalStackSlotPass."); } // Assign large stack objects first. for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock()) continue; if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) continue; if (RS && RS->isScavengingFrameIndex((int)i)) continue; if (MFI.isDeadObjectIndex(i)) continue; if (StackProtectorFI == (int)i || EHRegNodeFrameIndex == (int)i) continue; // Only allocate objects on the default stack. if (MFI.getStackID(i) != TargetStackID::Default) continue; switch (MFI.getObjectSSPLayout(i)) { case MachineFrameInfo::SSPLK_None: continue; case MachineFrameInfo::SSPLK_SmallArray: SmallArrayObjs.insert(i); continue; case MachineFrameInfo::SSPLK_AddrOf: AddrOfObjs.insert(i); continue; case MachineFrameInfo::SSPLK_LargeArray: LargeArrayObjs.insert(i); continue; } llvm_unreachable("Unexpected SSPLayoutKind."); } // We expect **all** the protected stack objects to be pre-allocated by // LocalStackSlotPass. If it turns out that PEI still has to allocate some // of them, we may end up messing up the expected order of the objects. if (MFI.getUseLocalStackAllocationBlock() && !(LargeArrayObjs.empty() && SmallArrayObjs.empty() && AddrOfObjs.empty())) llvm_unreachable("Found protected stack objects not pre-allocated by " "LocalStackSlotPass."); AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, Offset, MaxAlign, Skew); AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, Offset, MaxAlign, Skew); AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, Offset, MaxAlign, Skew); } SmallVector ObjectsToAllocate; // Then prepare to assign frame offsets to stack objects that are not used to // spill callee saved registers. for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock()) continue; if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) continue; if (RS && RS->isScavengingFrameIndex((int)i)) continue; if (MFI.isDeadObjectIndex(i)) continue; if (MFI.getStackProtectorIndex() == (int)i || EHRegNodeFrameIndex == (int)i) continue; if (ProtectedObjs.count(i)) continue; // Only allocate objects on the default stack. if (MFI.getStackID(i) != TargetStackID::Default) continue; // Add the objects that we need to allocate to our working set. ObjectsToAllocate.push_back(i); } // Allocate the EH registration node first if one is present. if (EHRegNodeFrameIndex != std::numeric_limits::max()) AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset, MaxAlign, Skew); // Give the targets a chance to order the objects the way they like it. if (MF.getTarget().getOptLevel() != CodeGenOpt::None && MF.getTarget().Options.StackSymbolOrdering) TFI.orderFrameObjects(MF, ObjectsToAllocate); // Keep track of which bytes in the fixed and callee-save range are used so we // can use the holes when allocating later stack objects. Only do this if // stack protector isn't being used and the target requests it and we're // optimizing. BitVector StackBytesFree; if (!ObjectsToAllocate.empty() && MF.getTarget().getOptLevel() != CodeGenOpt::None && MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(MF)) computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex, FixedCSEnd, StackBytesFree); // Now walk the objects and actually assign base offsets to them. for (auto &Object : ObjectsToAllocate) if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign, StackBytesFree)) AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign, Skew); // Make sure the special register scavenging spill slot is closest to the // stack pointer. if (RS && !EarlyScavengingSlots) { SmallVector SFIs; RS->getScavengingFrameIndices(SFIs); for (int SFI : SFIs) AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign, Skew); } if (!TFI.targetHandlesStackFrameRounding()) { // If we have reserved argument space for call sites in the function // immediately on entry to the current function, count it as part of the // overall stack size. if (MFI.adjustsStack() && TFI.hasReservedCallFrame(MF)) Offset += MFI.getMaxCallFrameSize(); // Round up the size to a multiple of the alignment. If the function has // any calls or alloca's, align to the target's StackAlignment value to // ensure that the callee's frame or the alloca data is suitably aligned; // otherwise, for leaf functions, align to the TransientStackAlignment // value. Align StackAlign; if (MFI.adjustsStack() || MFI.hasVarSizedObjects() || (RegInfo->hasStackRealignment(MF) && MFI.getObjectIndexEnd() != 0)) StackAlign = TFI.getStackAlign(); else StackAlign = TFI.getTransientStackAlign(); // If the frame pointer is eliminated, all frame offsets will be relative to // SP not FP. Align to MaxAlign so this works. StackAlign = std::max(StackAlign, MaxAlign); int64_t OffsetBeforeAlignment = Offset; Offset = alignTo(Offset, StackAlign, Skew); // If we have increased the offset to fulfill the alignment constrants, // then the scavenging spill slots may become harder to reach from the // stack pointer, float them so they stay close. if (StackGrowsDown && OffsetBeforeAlignment != Offset && RS && !EarlyScavengingSlots) { SmallVector SFIs; RS->getScavengingFrameIndices(SFIs); LLVM_DEBUG(if (!SFIs.empty()) llvm::dbgs() << "Adjusting emergency spill slots!\n";); int64_t Delta = Offset - OffsetBeforeAlignment; for (int SFI : SFIs) { LLVM_DEBUG(llvm::dbgs() << "Adjusting offset of emergency spill slot #" << SFI << " from " << MFI.getObjectOffset(SFI);); MFI.setObjectOffset(SFI, MFI.getObjectOffset(SFI) - Delta); LLVM_DEBUG(llvm::dbgs() << " to " << MFI.getObjectOffset(SFI) << "\n";); } } } // Update frame info to pretend that this is part of the stack... int64_t StackSize = Offset - LocalAreaOffset; MFI.setStackSize(StackSize); NumBytesStackSpace += StackSize; } /// insertPrologEpilogCode - Scan the function for modified callee saved /// registers, insert spill code for these callee saved registers, then add /// prolog and epilog code to the function. void PEI::insertPrologEpilogCode(MachineFunction &MF) { const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering(); // Add prologue to the function... for (MachineBasicBlock *SaveBlock : SaveBlocks) TFI.emitPrologue(MF, *SaveBlock); // Add epilogue to restore the callee-save registers in each exiting block. for (MachineBasicBlock *RestoreBlock : RestoreBlocks) TFI.emitEpilogue(MF, *RestoreBlock); // Zero call used registers before restoring callee-saved registers. insertZeroCallUsedRegs(MF); for (MachineBasicBlock *SaveBlock : SaveBlocks) TFI.inlineStackProbe(MF, *SaveBlock); // Emit additional code that is required to support segmented stacks, if // we've been asked for it. This, when linked with a runtime with support // for segmented stacks (libgcc is one), will result in allocating stack // space in small chunks instead of one large contiguous block. if (MF.shouldSplitStack()) { for (MachineBasicBlock *SaveBlock : SaveBlocks) TFI.adjustForSegmentedStacks(MF, *SaveBlock); } // Emit additional code that is required to explicitly handle the stack in // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The // approach is rather similar to that of Segmented Stacks, but it uses a // different conditional check and another BIF for allocating more stack // space. if (MF.getFunction().getCallingConv() == CallingConv::HiPE) for (MachineBasicBlock *SaveBlock : SaveBlocks) TFI.adjustForHiPEPrologue(MF, *SaveBlock); } /// insertZeroCallUsedRegs - Zero out call used registers. void PEI::insertZeroCallUsedRegs(MachineFunction &MF) { const Function &F = MF.getFunction(); if (!F.hasFnAttribute("zero-call-used-regs")) return; using namespace ZeroCallUsedRegs; ZeroCallUsedRegsKind ZeroRegsKind = StringSwitch( F.getFnAttribute("zero-call-used-regs").getValueAsString()) .Case("skip", ZeroCallUsedRegsKind::Skip) .Case("used-gpr-arg", ZeroCallUsedRegsKind::UsedGPRArg) .Case("used-gpr", ZeroCallUsedRegsKind::UsedGPR) .Case("used-arg", ZeroCallUsedRegsKind::UsedArg) .Case("used", ZeroCallUsedRegsKind::Used) .Case("all-gpr-arg", ZeroCallUsedRegsKind::AllGPRArg) .Case("all-gpr", ZeroCallUsedRegsKind::AllGPR) .Case("all-arg", ZeroCallUsedRegsKind::AllArg) .Case("all", ZeroCallUsedRegsKind::All); if (ZeroRegsKind == ZeroCallUsedRegsKind::Skip) return; const bool OnlyGPR = static_cast(ZeroRegsKind) & ONLY_GPR; const bool OnlyUsed = static_cast(ZeroRegsKind) & ONLY_USED; const bool OnlyArg = static_cast(ZeroRegsKind) & ONLY_ARG; const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); const BitVector AllocatableSet(TRI.getAllocatableSet(MF)); // Mark all used registers. BitVector UsedRegs(TRI.getNumRegs()); if (OnlyUsed) for (const MachineBasicBlock &MBB : MF) for (const MachineInstr &MI : MBB) for (const MachineOperand &MO : MI.operands()) { if (!MO.isReg()) continue; MCRegister Reg = MO.getReg(); if (AllocatableSet[Reg] && !MO.isImplicit() && (MO.isDef() || MO.isUse())) UsedRegs.set(Reg); } BitVector RegsToZero(TRI.getNumRegs()); for (MCRegister Reg : AllocatableSet.set_bits()) { // Skip over fixed registers. if (TRI.isFixedRegister(MF, Reg)) continue; // Want only general purpose registers. if (OnlyGPR && !TRI.isGeneralPurposeRegister(MF, Reg)) continue; // Want only used registers. if (OnlyUsed && !UsedRegs[Reg]) continue; // Want only registers used for arguments. if (OnlyArg && !TRI.isArgumentRegister(MF, Reg)) continue; RegsToZero.set(Reg); } // Don't clear registers that are live when leaving the function. for (const MachineBasicBlock &MBB : MF) for (const MachineInstr &MI : MBB.terminators()) { if (!MI.isReturn()) continue; for (const auto &MO : MI.operands()) { if (!MO.isReg()) continue; - for (MCPhysReg SReg : TRI.sub_and_superregs_inclusive(MO.getReg())) + MCRegister Reg = MO.getReg(); + + // This picks up sibling registers (e.q. %al -> %ah). + for (MCRegUnitIterator Unit(Reg, &TRI); Unit.isValid(); ++Unit) + RegsToZero.reset(*Unit); + + for (MCPhysReg SReg : TRI.sub_and_superregs_inclusive(Reg)) RegsToZero.reset(SReg); } } // Don't need to clear registers that are used/clobbered by terminating // instructions. for (const MachineBasicBlock &MBB : MF) { if (!MBB.isReturnBlock()) continue; MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator(); for (MachineBasicBlock::const_iterator I = MBBI, E = MBB.end(); I != E; ++I) { for (const MachineOperand &MO : I->operands()) { if (!MO.isReg()) continue; for (const MCPhysReg &Reg : TRI.sub_and_superregs_inclusive(MO.getReg())) RegsToZero.reset(Reg); } } } // Don't clear registers that must be preserved. for (const MCPhysReg *CSRegs = TRI.getCalleeSavedRegs(&MF); MCPhysReg CSReg = *CSRegs; ++CSRegs) for (MCRegister Reg : TRI.sub_and_superregs_inclusive(CSReg)) RegsToZero.reset(Reg); const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering(); for (MachineBasicBlock &MBB : MF) if (MBB.isReturnBlock()) TFI.emitZeroCallUsedRegs(RegsToZero, MBB); } /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical /// register references and actual offsets. void PEI::replaceFrameIndices(MachineFunction &MF) { const auto &ST = MF.getSubtarget(); const TargetFrameLowering &TFI = *ST.getFrameLowering(); if (!TFI.needsFrameIndexResolution(MF)) return; const TargetRegisterInfo *TRI = ST.getRegisterInfo(); // Allow the target to determine this after knowing the frame size. FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) || TRI->requiresFrameIndexReplacementScavenging(MF); // Store SPAdj at exit of a basic block. SmallVector SPState; SPState.resize(MF.getNumBlockIDs()); df_iterator_default_set Reachable; // Iterate over the reachable blocks in DFS order. for (auto DFI = df_ext_begin(&MF, Reachable), DFE = df_ext_end(&MF, Reachable); DFI != DFE; ++DFI) { int SPAdj = 0; // Check the exit state of the DFS stack predecessor. if (DFI.getPathLength() >= 2) { MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); assert(Reachable.count(StackPred) && "DFS stack predecessor is already visited.\n"); SPAdj = SPState[StackPred->getNumber()]; } MachineBasicBlock *BB = *DFI; replaceFrameIndices(BB, MF, SPAdj); SPState[BB->getNumber()] = SPAdj; } // Handle the unreachable blocks. for (auto &BB : MF) { if (Reachable.count(&BB)) // Already handled in DFS traversal. continue; int SPAdj = 0; replaceFrameIndices(&BB, MF, SPAdj); } } void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF, int &SPAdj) { assert(MF.getSubtarget().getRegisterInfo() && "getRegisterInfo() must be implemented!"); const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering(); if (RS && FrameIndexEliminationScavenging) RS->enterBasicBlock(*BB); bool InsideCallSequence = false; for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { if (TII.isFrameInstr(*I)) { InsideCallSequence = TII.isFrameSetup(*I); SPAdj += TII.getSPAdjust(*I); I = TFI->eliminateCallFramePseudoInstr(MF, *BB, I); continue; } MachineInstr &MI = *I; bool DoIncr = true; bool DidFinishLoop = true; for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { if (!MI.getOperand(i).isFI()) continue; // Frame indices in debug values are encoded in a target independent // way with simply the frame index and offset rather than any // target-specific addressing mode. if (MI.isDebugValue()) { MachineOperand &Op = MI.getOperand(i); assert( MI.isDebugOperand(&Op) && "Frame indices can only appear as a debug operand in a DBG_VALUE*" " machine instruction"); Register Reg; unsigned FrameIdx = Op.getIndex(); unsigned Size = MF.getFrameInfo().getObjectSize(FrameIdx); StackOffset Offset = TFI->getFrameIndexReference(MF, FrameIdx, Reg); Op.ChangeToRegister(Reg, false /*isDef*/); const DIExpression *DIExpr = MI.getDebugExpression(); // If we have a direct DBG_VALUE, and its location expression isn't // currently complex, then adding an offset will morph it into a // complex location that is interpreted as being a memory address. // This changes a pointer-valued variable to dereference that pointer, // which is incorrect. Fix by adding DW_OP_stack_value. if (MI.isNonListDebugValue()) { unsigned PrependFlags = DIExpression::ApplyOffset; if (!MI.isIndirectDebugValue() && !DIExpr->isComplex()) PrependFlags |= DIExpression::StackValue; // If we have DBG_VALUE that is indirect and has a Implicit location // expression need to insert a deref before prepending a Memory // location expression. Also after doing this we change the DBG_VALUE // to be direct. if (MI.isIndirectDebugValue() && DIExpr->isImplicit()) { SmallVector Ops = {dwarf::DW_OP_deref_size, Size}; bool WithStackValue = true; DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue); // Make the DBG_VALUE direct. MI.getDebugOffset().ChangeToRegister(0, false); } DIExpr = TRI.prependOffsetExpression(DIExpr, PrependFlags, Offset); } else { // The debug operand at DebugOpIndex was a frame index at offset // `Offset`; now the operand has been replaced with the frame // register, we must add Offset with `register x, plus Offset`. unsigned DebugOpIndex = MI.getDebugOperandIndex(&Op); SmallVector Ops; TRI.getOffsetOpcodes(Offset, Ops); DIExpr = DIExpression::appendOpsToArg(DIExpr, Ops, DebugOpIndex); } MI.getDebugExpressionOp().setMetadata(DIExpr); continue; } else if (MI.isDebugPHI()) { // Allow stack ref to continue onwards. continue; } // TODO: This code should be commoned with the code for // PATCHPOINT. There's no good reason for the difference in // implementation other than historical accident. The only // remaining difference is the unconditional use of the stack // pointer as the base register. if (MI.getOpcode() == TargetOpcode::STATEPOINT) { assert((!MI.isDebugValue() || i == 0) && "Frame indicies can only appear as the first operand of a " "DBG_VALUE machine instruction"); Register Reg; MachineOperand &Offset = MI.getOperand(i + 1); StackOffset refOffset = TFI->getFrameIndexReferencePreferSP( MF, MI.getOperand(i).getIndex(), Reg, /*IgnoreSPUpdates*/ false); assert(!refOffset.getScalable() && "Frame offsets with a scalable component are not supported"); Offset.setImm(Offset.getImm() + refOffset.getFixed() + SPAdj); MI.getOperand(i).ChangeToRegister(Reg, false /*isDef*/); continue; } // Some instructions (e.g. inline asm instructions) can have // multiple frame indices and/or cause eliminateFrameIndex // to insert more than one instruction. We need the register // scavenger to go through all of these instructions so that // it can update its register information. We keep the // iterator at the point before insertion so that we can // revisit them in full. bool AtBeginning = (I == BB->begin()); if (!AtBeginning) --I; // If this instruction has a FrameIndex operand, we need to // use that target machine register info object to eliminate // it. TRI.eliminateFrameIndex(MI, SPAdj, i, FrameIndexEliminationScavenging ? RS : nullptr); // Reset the iterator if we were at the beginning of the BB. if (AtBeginning) { I = BB->begin(); DoIncr = false; } DidFinishLoop = false; break; } // If we are looking at a call sequence, we need to keep track of // the SP adjustment made by each instruction in the sequence. // This includes both the frame setup/destroy pseudos (handled above), // as well as other instructions that have side effects w.r.t the SP. // Note that this must come after eliminateFrameIndex, because // if I itself referred to a frame index, we shouldn't count its own // adjustment. if (DidFinishLoop && InsideCallSequence) SPAdj += TII.getSPAdjust(MI); if (DoIncr && I != BB->end()) ++I; // Update register states. if (RS && FrameIndexEliminationScavenging && DidFinishLoop) RS->forward(MI); } } diff --git a/llvm/lib/CodeGen/RegAllocFast.cpp b/llvm/lib/CodeGen/RegAllocFast.cpp index 9e4e26f1392e..cb552f212fbb 100644 --- a/llvm/lib/CodeGen/RegAllocFast.cpp +++ b/llvm/lib/CodeGen/RegAllocFast.cpp @@ -1,1586 +1,1589 @@ //===- RegAllocFast.cpp - A fast register allocator for debug code --------===// // // 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 // //===----------------------------------------------------------------------===// // /// \file This register allocator allocates registers to a basic block at a /// time, attempting to keep values in registers and reusing registers as /// appropriate. // //===----------------------------------------------------------------------===// #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RegAllocCommon.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/CodeGen/RegisterClassInfo.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetOpcodes.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/InitializePasses.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include #include #include using namespace llvm; #define DEBUG_TYPE "regalloc" STATISTIC(NumStores, "Number of stores added"); STATISTIC(NumLoads , "Number of loads added"); STATISTIC(NumCoalesced, "Number of copies coalesced"); // FIXME: Remove this switch when all testcases are fixed! static cl::opt IgnoreMissingDefs("rafast-ignore-missing-defs", cl::Hidden); static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); namespace { class RegAllocFast : public MachineFunctionPass { public: static char ID; RegAllocFast(const RegClassFilterFunc F = allocateAllRegClasses, bool ClearVirtRegs_ = true) : MachineFunctionPass(ID), ShouldAllocateClass(F), StackSlotForVirtReg(-1), ClearVirtRegs(ClearVirtRegs_) { } private: MachineFrameInfo *MFI; MachineRegisterInfo *MRI; const TargetRegisterInfo *TRI; const TargetInstrInfo *TII; RegisterClassInfo RegClassInfo; const RegClassFilterFunc ShouldAllocateClass; /// Basic block currently being allocated. MachineBasicBlock *MBB; /// Maps virtual regs to the frame index where these values are spilled. IndexedMap StackSlotForVirtReg; bool ClearVirtRegs; /// Everything we know about a live virtual register. struct LiveReg { MachineInstr *LastUse = nullptr; ///< Last instr to use reg. Register VirtReg; ///< Virtual register number. MCPhysReg PhysReg = 0; ///< Currently held here. bool LiveOut = false; ///< Register is possibly live out. bool Reloaded = false; ///< Register was reloaded. bool Error = false; ///< Could not allocate. explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {} unsigned getSparseSetIndex() const { return Register::virtReg2Index(VirtReg); } }; using LiveRegMap = SparseSet; /// This map contains entries for each virtual register that is currently /// available in a physical register. LiveRegMap LiveVirtRegs; /// Stores assigned virtual registers present in the bundle MI. DenseMap BundleVirtRegsMap; DenseMap> LiveDbgValueMap; /// List of DBG_VALUE that we encountered without the vreg being assigned /// because they were placed after the last use of the vreg. DenseMap> DanglingDbgValues; /// Has a bit set for every virtual register for which it was determined /// that it is alive across blocks. BitVector MayLiveAcrossBlocks; /// State of a register unit. enum RegUnitState { /// A free register is not currently in use and can be allocated /// immediately without checking aliases. regFree, /// A pre-assigned register has been assigned before register allocation /// (e.g., setting up a call parameter). regPreAssigned, /// Used temporarily in reloadAtBegin() to mark register units that are /// live-in to the basic block. regLiveIn, /// A register state may also be a virtual register number, indication /// that the physical register is currently allocated to a virtual /// register. In that case, LiveVirtRegs contains the inverse mapping. }; /// Maps each physical register to a RegUnitState enum or virtual register. std::vector RegUnitStates; SmallVector Coalesced; using RegUnitSet = SparseSet>; /// Set of register units that are used in the current instruction, and so /// cannot be allocated. RegUnitSet UsedInInstr; RegUnitSet PhysRegUses; SmallVector DefOperandIndexes; // Register masks attached to the current instruction. SmallVector RegMasks; void setPhysRegState(MCPhysReg PhysReg, unsigned NewState); bool isPhysRegFree(MCPhysReg PhysReg) const; /// Mark a physreg as used in this instruction. void markRegUsedInInstr(MCPhysReg PhysReg) { for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) UsedInInstr.insert(*Units); } // Check if physreg is clobbered by instruction's regmask(s). bool isClobberedByRegMasks(MCPhysReg PhysReg) const { return llvm::any_of(RegMasks, [PhysReg](const uint32_t *Mask) { return MachineOperand::clobbersPhysReg(Mask, PhysReg); }); } /// Check if a physreg or any of its aliases are used in this instruction. bool isRegUsedInInstr(MCPhysReg PhysReg, bool LookAtPhysRegUses) const { if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg)) return true; for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { if (UsedInInstr.count(*Units)) return true; if (LookAtPhysRegUses && PhysRegUses.count(*Units)) return true; } return false; } /// Mark physical register as being used in a register use operand. /// This is only used by the special livethrough handling code. void markPhysRegUsedInInstr(MCPhysReg PhysReg) { for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) PhysRegUses.insert(*Units); } /// Remove mark of physical register being used in the instruction. void unmarkRegUsedInInstr(MCPhysReg PhysReg) { for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) UsedInInstr.erase(*Units); } enum : unsigned { spillClean = 50, spillDirty = 100, spillPrefBonus = 20, spillImpossible = ~0u }; public: StringRef getPassName() const override { return "Fast Register Allocator"; } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); } MachineFunctionProperties getRequiredProperties() const override { return MachineFunctionProperties().set( MachineFunctionProperties::Property::NoPHIs); } MachineFunctionProperties getSetProperties() const override { if (ClearVirtRegs) { return MachineFunctionProperties().set( MachineFunctionProperties::Property::NoVRegs); } return MachineFunctionProperties(); } MachineFunctionProperties getClearedProperties() const override { return MachineFunctionProperties().set( MachineFunctionProperties::Property::IsSSA); } private: bool runOnMachineFunction(MachineFunction &MF) override; void allocateBasicBlock(MachineBasicBlock &MBB); void addRegClassDefCounts(std::vector &RegClassDefCounts, Register Reg) const; void allocateInstruction(MachineInstr &MI); void handleDebugValue(MachineInstr &MI); void handleBundle(MachineInstr &MI); bool usePhysReg(MachineInstr &MI, MCPhysReg PhysReg); bool definePhysReg(MachineInstr &MI, MCPhysReg PhysReg); bool displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg); void freePhysReg(MCPhysReg PhysReg); unsigned calcSpillCost(MCPhysReg PhysReg) const; LiveRegMap::iterator findLiveVirtReg(Register VirtReg) { return LiveVirtRegs.find(Register::virtReg2Index(VirtReg)); } LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const { return LiveVirtRegs.find(Register::virtReg2Index(VirtReg)); } void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCPhysReg PhysReg); void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint, bool LookAtPhysRegUses = false); void allocVirtRegUndef(MachineOperand &MO); void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg, MCPhysReg Reg); void defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg); void defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg, bool LookAtPhysRegUses = false); void useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg); MachineBasicBlock::iterator getMBBBeginInsertionPoint(MachineBasicBlock &MBB, SmallSet &PrologLiveIns) const; void reloadAtBegin(MachineBasicBlock &MBB); void setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg); Register traceCopies(Register VirtReg) const; Register traceCopyChain(Register Reg) const; int getStackSpaceFor(Register VirtReg); void spill(MachineBasicBlock::iterator Before, Register VirtReg, MCPhysReg AssignedReg, bool Kill, bool LiveOut); void reload(MachineBasicBlock::iterator Before, Register VirtReg, MCPhysReg PhysReg); bool mayLiveOut(Register VirtReg); bool mayLiveIn(Register VirtReg); void dumpState() const; }; } // end anonymous namespace char RegAllocFast::ID = 0; INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false, false) void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) { for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) RegUnitStates[*UI] = NewState; } bool RegAllocFast::isPhysRegFree(MCPhysReg PhysReg) const { for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) { if (RegUnitStates[*UI] != regFree) return false; } return true; } /// This allocates space for the specified virtual register to be held on the /// stack. int RegAllocFast::getStackSpaceFor(Register VirtReg) { // Find the location Reg would belong... int SS = StackSlotForVirtReg[VirtReg]; // Already has space allocated? if (SS != -1) return SS; // Allocate a new stack object for this spill location... const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); unsigned Size = TRI->getSpillSize(RC); Align Alignment = TRI->getSpillAlign(RC); int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment); // Assign the slot. StackSlotForVirtReg[VirtReg] = FrameIdx; return FrameIdx; } static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B) { auto MBBEnd = MBB.end(); if (B == MBBEnd) return true; MachineBasicBlock::const_iterator I = MBB.begin(); for (; &*I != A && &*I != B; ++I) ; return &*I == A; } /// Returns false if \p VirtReg is known to not live out of the current block. bool RegAllocFast::mayLiveOut(Register VirtReg) { if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) { // Cannot be live-out if there are no successors. return !MBB->succ_empty(); } const MachineInstr *SelfLoopDef = nullptr; // If this block loops back to itself, it is necessary to check whether the // use comes after the def. if (MBB->isSuccessor(MBB)) { // Find the first def in the self loop MBB. for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) { if (DefInst.getParent() != MBB) { MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg)); return true; } else { if (!SelfLoopDef || dominates(*MBB, DefInst.getIterator(), SelfLoopDef)) SelfLoopDef = &DefInst; } } if (!SelfLoopDef) { MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg)); return true; } } // See if the first \p Limit uses of the register are all in the current // block. static const unsigned Limit = 8; unsigned C = 0; for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) { if (UseInst.getParent() != MBB || ++C >= Limit) { MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg)); // Cannot be live-out if there are no successors. return !MBB->succ_empty(); } if (SelfLoopDef) { // Try to handle some simple cases to avoid spilling and reloading every // value inside a self looping block. if (SelfLoopDef == &UseInst || !dominates(*MBB, SelfLoopDef->getIterator(), UseInst.getIterator())) { MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg)); return true; } } } return false; } /// Returns false if \p VirtReg is known to not be live into the current block. bool RegAllocFast::mayLiveIn(Register VirtReg) { if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) return !MBB->pred_empty(); // See if the first \p Limit def of the register are all in the current block. static const unsigned Limit = 8; unsigned C = 0; for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) { if (DefInst.getParent() != MBB || ++C >= Limit) { MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg)); return !MBB->pred_empty(); } } return false; } /// Insert spill instruction for \p AssignedReg before \p Before. Update /// DBG_VALUEs with \p VirtReg operands with the stack slot. void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg, MCPhysReg AssignedReg, bool Kill, bool LiveOut) { LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI) << " in " << printReg(AssignedReg, TRI)); int FI = getStackSpaceFor(VirtReg); LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n'); const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI); ++NumStores; MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator(); // When we spill a virtual register, we will have spill instructions behind // every definition of it, meaning we can switch all the DBG_VALUEs over // to just reference the stack slot. SmallVectorImpl &LRIDbgOperands = LiveDbgValueMap[VirtReg]; SmallMapVector, 2> SpilledOperandsMap; for (MachineOperand *MO : LRIDbgOperands) SpilledOperandsMap[MO->getParent()].push_back(MO); for (auto MISpilledOperands : SpilledOperandsMap) { MachineInstr &DBG = *MISpilledOperands.first; + // We don't have enough support for tracking operands of DBG_VALUE_LISTs. + if (DBG.isDebugValueList()) + continue; MachineInstr *NewDV = buildDbgValueForSpill( *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second); assert(NewDV->getParent() == MBB && "dangling parent pointer"); (void)NewDV; LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV); if (LiveOut) { // We need to insert a DBG_VALUE at the end of the block if the spill slot // is live out, but there is another use of the value after the // spill. This will allow LiveDebugValues to see the correct live out // value to propagate to the successors. MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV); MBB->insert(FirstTerm, ClonedDV); LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n"); } // Rewrite unassigned dbg_values to use the stack slot. // TODO We can potentially do this for list debug values as well if we know // how the dbg_values are getting unassigned. if (DBG.isNonListDebugValue()) { MachineOperand &MO = DBG.getDebugOperand(0); if (MO.isReg() && MO.getReg() == 0) { updateDbgValueForSpill(DBG, FI, 0); } } } // Now this register is spilled there is should not be any DBG_VALUE // pointing to this register because they are all pointing to spilled value // now. LRIDbgOperands.clear(); } /// Insert reload instruction for \p PhysReg before \p Before. void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg, MCPhysReg PhysReg) { LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into " << printReg(PhysReg, TRI) << '\n'); int FI = getStackSpaceFor(VirtReg); const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI); ++NumLoads; } /// Get basic block begin insertion point. /// This is not just MBB.begin() because surprisingly we have EH_LABEL /// instructions marking the begin of a basic block. This means we must insert /// new instructions after such labels... MachineBasicBlock::iterator RegAllocFast::getMBBBeginInsertionPoint( MachineBasicBlock &MBB, SmallSet &PrologLiveIns) const { MachineBasicBlock::iterator I = MBB.begin(); while (I != MBB.end()) { if (I->isLabel()) { ++I; continue; } // Most reloads should be inserted after prolog instructions. if (!TII->isBasicBlockPrologue(*I)) break; // However if a prolog instruction reads a register that needs to be // reloaded, the reload should be inserted before the prolog. for (MachineOperand &MO : I->operands()) { if (MO.isReg()) PrologLiveIns.insert(MO.getReg()); } ++I; } return I; } /// Reload all currently assigned virtual registers. void RegAllocFast::reloadAtBegin(MachineBasicBlock &MBB) { if (LiveVirtRegs.empty()) return; for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) { MCPhysReg Reg = P.PhysReg; // Set state to live-in. This possibly overrides mappings to virtual // registers but we don't care anymore at this point. setPhysRegState(Reg, regLiveIn); } SmallSet PrologLiveIns; // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order // of spilling here is deterministic, if arbitrary. MachineBasicBlock::iterator InsertBefore = getMBBBeginInsertionPoint(MBB, PrologLiveIns); for (const LiveReg &LR : LiveVirtRegs) { MCPhysReg PhysReg = LR.PhysReg; if (PhysReg == 0) continue; MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI); if (RegUnitStates[FirstUnit] == regLiveIn) continue; assert((&MBB != &MBB.getParent()->front() || IgnoreMissingDefs) && "no reload in start block. Missing vreg def?"); if (PrologLiveIns.count(PhysReg)) { // FIXME: Theoretically this should use an insert point skipping labels // but I'm not sure how labels should interact with prolog instruction // that need reloads. reload(MBB.begin(), LR.VirtReg, PhysReg); } else reload(InsertBefore, LR.VirtReg, PhysReg); } LiveVirtRegs.clear(); } /// Handle the direct use of a physical register. Check that the register is /// not used by a virtreg. Kill the physreg, marking it free. This may add /// implicit kills to MO->getParent() and invalidate MO. bool RegAllocFast::usePhysReg(MachineInstr &MI, MCPhysReg Reg) { assert(Register::isPhysicalRegister(Reg) && "expected physreg"); bool displacedAny = displacePhysReg(MI, Reg); setPhysRegState(Reg, regPreAssigned); markRegUsedInInstr(Reg); return displacedAny; } bool RegAllocFast::definePhysReg(MachineInstr &MI, MCPhysReg Reg) { bool displacedAny = displacePhysReg(MI, Reg); setPhysRegState(Reg, regPreAssigned); return displacedAny; } /// Mark PhysReg as reserved or free after spilling any virtregs. This is very /// similar to defineVirtReg except the physreg is reserved instead of /// allocated. bool RegAllocFast::displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg) { bool displacedAny = false; for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) { unsigned Unit = *UI; switch (unsigned VirtReg = RegUnitStates[Unit]) { default: { LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); assert(LRI != LiveVirtRegs.end() && "datastructures in sync"); MachineBasicBlock::iterator ReloadBefore = std::next((MachineBasicBlock::iterator)MI.getIterator()); reload(ReloadBefore, VirtReg, LRI->PhysReg); setPhysRegState(LRI->PhysReg, regFree); LRI->PhysReg = 0; LRI->Reloaded = true; displacedAny = true; break; } case regPreAssigned: RegUnitStates[Unit] = regFree; displacedAny = true; break; case regFree: break; } } return displacedAny; } void RegAllocFast::freePhysReg(MCPhysReg PhysReg) { LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':'); MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI); switch (unsigned VirtReg = RegUnitStates[FirstUnit]) { case regFree: LLVM_DEBUG(dbgs() << '\n'); return; case regPreAssigned: LLVM_DEBUG(dbgs() << '\n'); setPhysRegState(PhysReg, regFree); return; default: { LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); assert(LRI != LiveVirtRegs.end()); LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n'); setPhysRegState(LRI->PhysReg, regFree); LRI->PhysReg = 0; } return; } } /// Return the cost of spilling clearing out PhysReg and aliases so it is free /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases /// disabled - it can be allocated directly. /// \returns spillImpossible when PhysReg or an alias can't be spilled. unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const { for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) { switch (unsigned VirtReg = RegUnitStates[*UI]) { case regFree: break; case regPreAssigned: LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned " << printReg(PhysReg, TRI) << '\n'); return spillImpossible; default: { bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 || findLiveVirtReg(VirtReg)->LiveOut; return SureSpill ? spillClean : spillDirty; } } } return 0; } void RegAllocFast::assignDanglingDebugValues(MachineInstr &Definition, Register VirtReg, MCPhysReg Reg) { auto UDBGValIter = DanglingDbgValues.find(VirtReg); if (UDBGValIter == DanglingDbgValues.end()) return; SmallVectorImpl &Dangling = UDBGValIter->second; for (MachineInstr *DbgValue : Dangling) { assert(DbgValue->isDebugValue()); if (!DbgValue->hasDebugOperandForReg(VirtReg)) continue; // Test whether the physreg survives from the definition to the DBG_VALUE. MCPhysReg SetToReg = Reg; unsigned Limit = 20; for (MachineBasicBlock::iterator I = std::next(Definition.getIterator()), E = DbgValue->getIterator(); I != E; ++I) { if (I->modifiesRegister(Reg, TRI) || --Limit == 0) { LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue << '\n'); SetToReg = 0; break; } } for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(VirtReg)) { MO.setReg(SetToReg); if (SetToReg != 0) MO.setIsRenamable(); } } Dangling.clear(); } /// This method updates local state so that we know that PhysReg is the /// proper container for VirtReg now. The physical register must not be used /// for anything else when this is called. void RegAllocFast::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR, MCPhysReg PhysReg) { Register VirtReg = LR.VirtReg; LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to " << printReg(PhysReg, TRI) << '\n'); assert(LR.PhysReg == 0 && "Already assigned a physreg"); assert(PhysReg != 0 && "Trying to assign no register"); LR.PhysReg = PhysReg; setPhysRegState(PhysReg, VirtReg); assignDanglingDebugValues(AtMI, VirtReg, PhysReg); } static bool isCoalescable(const MachineInstr &MI) { return MI.isFullCopy(); } Register RegAllocFast::traceCopyChain(Register Reg) const { static const unsigned ChainLengthLimit = 3; unsigned C = 0; do { if (Reg.isPhysical()) return Reg; assert(Reg.isVirtual()); MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg); if (!VRegDef || !isCoalescable(*VRegDef)) return 0; Reg = VRegDef->getOperand(1).getReg(); } while (++C <= ChainLengthLimit); return 0; } /// Check if any of \p VirtReg's definitions is a copy. If it is follow the /// chain of copies to check whether we reach a physical register we can /// coalesce with. Register RegAllocFast::traceCopies(Register VirtReg) const { static const unsigned DefLimit = 3; unsigned C = 0; for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) { if (isCoalescable(MI)) { Register Reg = MI.getOperand(1).getReg(); Reg = traceCopyChain(Reg); if (Reg.isValid()) return Reg; } if (++C >= DefLimit) break; } return Register(); } /// Allocates a physical register for VirtReg. void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint0, bool LookAtPhysRegUses) { const Register VirtReg = LR.VirtReg; assert(LR.PhysReg == 0); const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg) << " in class " << TRI->getRegClassName(&RC) << " with hint " << printReg(Hint0, TRI) << '\n'); // Take hint when possible. if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) && !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) { // Take hint if the register is currently free. if (isPhysRegFree(Hint0)) { LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI) << '\n'); assignVirtToPhysReg(MI, LR, Hint0); return; } else { LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI) << " occupied\n"); } } else { Hint0 = Register(); } // Try other hint. Register Hint1 = traceCopies(VirtReg); if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) && !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) { // Take hint if the register is currently free. if (isPhysRegFree(Hint1)) { LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI) << '\n'); assignVirtToPhysReg(MI, LR, Hint1); return; } else { LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI) << " occupied\n"); } } else { Hint1 = Register(); } MCPhysReg BestReg = 0; unsigned BestCost = spillImpossible; ArrayRef AllocationOrder = RegClassInfo.getOrder(&RC); for (MCPhysReg PhysReg : AllocationOrder) { LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' '); if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) { LLVM_DEBUG(dbgs() << "already used in instr.\n"); continue; } unsigned Cost = calcSpillCost(PhysReg); LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n'); // Immediate take a register with cost 0. if (Cost == 0) { assignVirtToPhysReg(MI, LR, PhysReg); return; } if (PhysReg == Hint0 || PhysReg == Hint1) Cost -= spillPrefBonus; if (Cost < BestCost) { BestReg = PhysReg; BestCost = Cost; } } if (!BestReg) { // Nothing we can do: Report an error and keep going with an invalid // allocation. if (MI.isInlineAsm()) MI.emitError("inline assembly requires more registers than available"); else MI.emitError("ran out of registers during register allocation"); LR.Error = true; LR.PhysReg = 0; return; } displacePhysReg(MI, BestReg); assignVirtToPhysReg(MI, LR, BestReg); } void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) { assert(MO.isUndef() && "expected undef use"); Register VirtReg = MO.getReg(); assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg"); LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg); MCPhysReg PhysReg; if (LRI != LiveVirtRegs.end() && LRI->PhysReg) { PhysReg = LRI->PhysReg; } else { const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); ArrayRef AllocationOrder = RegClassInfo.getOrder(&RC); assert(!AllocationOrder.empty() && "Allocation order must not be empty"); PhysReg = AllocationOrder[0]; } unsigned SubRegIdx = MO.getSubReg(); if (SubRegIdx != 0) { PhysReg = TRI->getSubReg(PhysReg, SubRegIdx); MO.setSubReg(0); } MO.setReg(PhysReg); MO.setIsRenamable(true); } /// Variation of defineVirtReg() with special handling for livethrough regs /// (tied or earlyclobber) that may interfere with preassigned uses. void RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg) { LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg); if (LRI != LiveVirtRegs.end()) { MCPhysReg PrevReg = LRI->PhysReg; if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) { LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI) << " (tied/earlyclobber resolution)\n"); freePhysReg(PrevReg); LRI->PhysReg = 0; allocVirtReg(MI, *LRI, 0, true); MachineBasicBlock::iterator InsertBefore = std::next((MachineBasicBlock::iterator)MI.getIterator()); LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to " << printReg(PrevReg, TRI) << '\n'); BuildMI(*MBB, InsertBefore, MI.getDebugLoc(), TII->get(TargetOpcode::COPY), PrevReg) .addReg(LRI->PhysReg, llvm::RegState::Kill); } MachineOperand &MO = MI.getOperand(OpNum); if (MO.getSubReg() && !MO.isUndef()) { LRI->LastUse = &MI; } } return defineVirtReg(MI, OpNum, VirtReg, true); } /// Allocates a register for VirtReg definition. Typically the register is /// already assigned from a use of the virtreg, however we still need to /// perform an allocation if: /// - It is a dead definition without any uses. /// - The value is live out and all uses are in different basic blocks. void RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg, bool LookAtPhysRegUses) { assert(VirtReg.isVirtual() && "Not a virtual register"); MachineOperand &MO = MI.getOperand(OpNum); LiveRegMap::iterator LRI; bool New; std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); if (New) { if (!MO.isDead()) { if (mayLiveOut(VirtReg)) { LRI->LiveOut = true; } else { // It is a dead def without the dead flag; add the flag now. MO.setIsDead(true); } } } if (LRI->PhysReg == 0) allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses); else { assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) && "TODO: preassign mismatch"); LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI) << " use existing assignment to " << printReg(LRI->PhysReg, TRI) << '\n'); } MCPhysReg PhysReg = LRI->PhysReg; assert(PhysReg != 0 && "Register not assigned"); if (LRI->Reloaded || LRI->LiveOut) { if (!MI.isImplicitDef()) { MachineBasicBlock::iterator SpillBefore = std::next((MachineBasicBlock::iterator)MI.getIterator()); LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut << " RL: " << LRI->Reloaded << '\n'); bool Kill = LRI->LastUse == nullptr; spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut); LRI->LastUse = nullptr; } LRI->LiveOut = false; LRI->Reloaded = false; } if (MI.getOpcode() == TargetOpcode::BUNDLE) { BundleVirtRegsMap[VirtReg] = PhysReg; } markRegUsedInInstr(PhysReg); setPhysReg(MI, MO, PhysReg); } /// Allocates a register for a VirtReg use. void RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg) { assert(VirtReg.isVirtual() && "Not a virtual register"); MachineOperand &MO = MI.getOperand(OpNum); LiveRegMap::iterator LRI; bool New; std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg)); if (New) { MachineOperand &MO = MI.getOperand(OpNum); if (!MO.isKill()) { if (mayLiveOut(VirtReg)) { LRI->LiveOut = true; } else { // It is a last (killing) use without the kill flag; add the flag now. MO.setIsKill(true); } } } else { assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag"); } // If necessary allocate a register. if (LRI->PhysReg == 0) { assert(!MO.isTied() && "tied op should be allocated"); Register Hint; if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) { Hint = MI.getOperand(0).getReg(); assert(Hint.isPhysical() && "Copy destination should already be assigned"); } allocVirtReg(MI, *LRI, Hint, false); if (LRI->Error) { const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg); ArrayRef AllocationOrder = RegClassInfo.getOrder(&RC); setPhysReg(MI, MO, *AllocationOrder.begin()); return; } } LRI->LastUse = &MI; if (MI.getOpcode() == TargetOpcode::BUNDLE) { BundleVirtRegsMap[VirtReg] = LRI->PhysReg; } markRegUsedInInstr(LRI->PhysReg); setPhysReg(MI, MO, LRI->PhysReg); } /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This /// may invalidate any operand pointers. Return true if the operand kills its /// register. void RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg) { if (!MO.getSubReg()) { MO.setReg(PhysReg); MO.setIsRenamable(true); return; } // Handle subregister index. MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : MCRegister()); MO.setIsRenamable(true); // Note: We leave the subreg number around a little longer in case of defs. // This is so that the register freeing logic in allocateInstruction can still // recognize this as subregister defs. The code there will clear the number. if (!MO.isDef()) MO.setSubReg(0); // A kill flag implies killing the full register. Add corresponding super // register kill. if (MO.isKill()) { MI.addRegisterKilled(PhysReg, TRI, true); return; } // A of a sub-register requires an implicit def of the full // register. if (MO.isDef() && MO.isUndef()) { if (MO.isDead()) MI.addRegisterDead(PhysReg, TRI, true); else MI.addRegisterDefined(PhysReg, TRI); } } #ifndef NDEBUG void RegAllocFast::dumpState() const { for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE; ++Unit) { switch (unsigned VirtReg = RegUnitStates[Unit]) { case regFree: break; case regPreAssigned: dbgs() << " " << printRegUnit(Unit, TRI) << "[P]"; break; case regLiveIn: llvm_unreachable("Should not have regLiveIn in map"); default: { dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg); LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg); assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry"); if (I->LiveOut || I->Reloaded) { dbgs() << '['; if (I->LiveOut) dbgs() << 'O'; if (I->Reloaded) dbgs() << 'R'; dbgs() << ']'; } assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present"); break; } } } dbgs() << '\n'; // Check that LiveVirtRegs is the inverse. for (const LiveReg &LR : LiveVirtRegs) { Register VirtReg = LR.VirtReg; assert(VirtReg.isVirtual() && "Bad map key"); MCPhysReg PhysReg = LR.PhysReg; if (PhysReg != 0) { assert(Register::isPhysicalRegister(PhysReg) && "mapped to physreg"); for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) { assert(RegUnitStates[*UI] == VirtReg && "inverse map valid"); } } } } #endif /// Count number of defs consumed from each register class by \p Reg void RegAllocFast::addRegClassDefCounts(std::vector &RegClassDefCounts, Register Reg) const { assert(RegClassDefCounts.size() == TRI->getNumRegClasses()); if (Reg.isVirtual()) { const TargetRegisterClass *OpRC = MRI->getRegClass(Reg); for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses(); RCIdx != RCIdxEnd; ++RCIdx) { const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx); // FIXME: Consider aliasing sub/super registers. if (OpRC->hasSubClassEq(IdxRC)) ++RegClassDefCounts[RCIdx]; } return; } for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses(); RCIdx != RCIdxEnd; ++RCIdx) { const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx); for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) { if (IdxRC->contains(*Alias)) { ++RegClassDefCounts[RCIdx]; break; } } } } void RegAllocFast::allocateInstruction(MachineInstr &MI) { // The basic algorithm here is: // 1. Mark registers of def operands as free // 2. Allocate registers to use operands and place reload instructions for // registers displaced by the allocation. // // However we need to handle some corner cases: // - pre-assigned defs and uses need to be handled before the other def/use // operands are processed to avoid the allocation heuristics clashing with // the pre-assignment. // - The "free def operands" step has to come last instead of first for tied // operands and early-clobbers. UsedInInstr.clear(); RegMasks.clear(); BundleVirtRegsMap.clear(); auto TiedOpIsUndef = [&](const MachineOperand &MO, unsigned Idx) { assert(MO.isTied()); unsigned TiedIdx = MI.findTiedOperandIdx(Idx); const MachineOperand &TiedMO = MI.getOperand(TiedIdx); return TiedMO.isUndef(); }; // Scan for special cases; Apply pre-assigned register defs to state. bool HasPhysRegUse = false; bool HasRegMask = false; bool HasVRegDef = false; bool HasDef = false; bool HasEarlyClobber = false; bool NeedToAssignLiveThroughs = false; for (unsigned I = 0; I < MI.getNumOperands(); ++I) { MachineOperand &MO = MI.getOperand(I); if (MO.isReg()) { Register Reg = MO.getReg(); if (Reg.isVirtual()) { if (MO.isDef()) { HasDef = true; HasVRegDef = true; if (MO.isEarlyClobber()) { HasEarlyClobber = true; NeedToAssignLiveThroughs = true; } if ((MO.isTied() && !TiedOpIsUndef(MO, I)) || (MO.getSubReg() != 0 && !MO.isUndef())) NeedToAssignLiveThroughs = true; } } else if (Reg.isPhysical()) { if (!MRI->isReserved(Reg)) { if (MO.isDef()) { HasDef = true; bool displacedAny = definePhysReg(MI, Reg); if (MO.isEarlyClobber()) HasEarlyClobber = true; if (!displacedAny) MO.setIsDead(true); } if (MO.readsReg()) HasPhysRegUse = true; } } } else if (MO.isRegMask()) { HasRegMask = true; RegMasks.push_back(MO.getRegMask()); } } // Allocate virtreg defs. if (HasDef) { if (HasVRegDef) { // Special handling for early clobbers, tied operands or subregister defs: // Compared to "normal" defs these: // - Must not use a register that is pre-assigned for a use operand. // - In order to solve tricky inline assembly constraints we change the // heuristic to figure out a good operand order before doing // assignments. if (NeedToAssignLiveThroughs) { DefOperandIndexes.clear(); PhysRegUses.clear(); // Track number of defs which may consume a register from the class. std::vector RegClassDefCounts(TRI->getNumRegClasses(), 0); assert(RegClassDefCounts[0] == 0); LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n"); for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) { const MachineOperand &MO = MI.getOperand(I); if (!MO.isReg()) continue; Register Reg = MO.getReg(); if (MO.readsReg()) { if (Reg.isPhysical()) { LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI) << '\n'); markPhysRegUsedInInstr(Reg); } } if (MO.isDef()) { if (Reg.isVirtual()) DefOperandIndexes.push_back(I); addRegClassDefCounts(RegClassDefCounts, Reg); } } llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) { const MachineOperand &MO0 = MI.getOperand(I0); const MachineOperand &MO1 = MI.getOperand(I1); Register Reg0 = MO0.getReg(); Register Reg1 = MO1.getReg(); const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0); const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1); // Identify regclass that are easy to use up completely just in this // instruction. unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size(); unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size(); bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()]; bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()]; if (SmallClass0 > SmallClass1) return true; if (SmallClass0 < SmallClass1) return false; // Allocate early clobbers and livethrough operands first. bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() || (MO0.getSubReg() == 0 && !MO0.isUndef()); bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() || (MO1.getSubReg() == 0 && !MO1.isUndef()); if (Livethrough0 > Livethrough1) return true; if (Livethrough0 < Livethrough1) return false; // Tie-break rule: operand index. return I0 < I1; }); for (uint16_t OpIdx : DefOperandIndexes) { MachineOperand &MO = MI.getOperand(OpIdx); LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n'); unsigned Reg = MO.getReg(); if (MO.isEarlyClobber() || (MO.isTied() && !TiedOpIsUndef(MO, OpIdx)) || (MO.getSubReg() && !MO.isUndef())) { defineLiveThroughVirtReg(MI, OpIdx, Reg); } else { defineVirtReg(MI, OpIdx, Reg); } } } else { // Assign virtual register defs. for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) { MachineOperand &MO = MI.getOperand(I); if (!MO.isReg() || !MO.isDef()) continue; Register Reg = MO.getReg(); if (Reg.isVirtual()) defineVirtReg(MI, I, Reg); } } } // Free registers occupied by defs. // Iterate operands in reverse order, so we see the implicit super register // defs first (we added them earlier in case of ). for (signed I = MI.getNumOperands() - 1; I >= 0; --I) { MachineOperand &MO = MI.getOperand(I); if (!MO.isReg() || !MO.isDef()) continue; // subreg defs don't free the full register. We left the subreg number // around as a marker in setPhysReg() to recognize this case here. if (MO.getSubReg() != 0) { MO.setSubReg(0); continue; } assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) && "tied def assigned to clobbered register"); // Do not free tied operands and early clobbers. if ((MO.isTied() && !TiedOpIsUndef(MO, I)) || MO.isEarlyClobber()) continue; Register Reg = MO.getReg(); if (!Reg) continue; assert(Reg.isPhysical()); if (MRI->isReserved(Reg)) continue; freePhysReg(Reg); unmarkRegUsedInInstr(Reg); } } // Displace clobbered registers. if (HasRegMask) { assert(!RegMasks.empty() && "expected RegMask"); // MRI bookkeeping. for (const auto *RM : RegMasks) MRI->addPhysRegsUsedFromRegMask(RM); // Displace clobbered registers. for (const LiveReg &LR : LiveVirtRegs) { MCPhysReg PhysReg = LR.PhysReg; if (PhysReg != 0 && isClobberedByRegMasks(PhysReg)) displacePhysReg(MI, PhysReg); } } // Apply pre-assigned register uses to state. if (HasPhysRegUse) { for (MachineOperand &MO : MI.operands()) { if (!MO.isReg() || !MO.readsReg()) continue; Register Reg = MO.getReg(); if (!Reg.isPhysical()) continue; if (MRI->isReserved(Reg)) continue; bool displacedAny = usePhysReg(MI, Reg); if (!displacedAny && !MRI->isReserved(Reg)) MO.setIsKill(true); } } // Allocate virtreg uses and insert reloads as necessary. bool HasUndefUse = false; for (unsigned I = 0; I < MI.getNumOperands(); ++I) { MachineOperand &MO = MI.getOperand(I); if (!MO.isReg() || !MO.isUse()) continue; Register Reg = MO.getReg(); if (!Reg.isVirtual()) continue; if (MO.isUndef()) { HasUndefUse = true; continue; } // Populate MayLiveAcrossBlocks in case the use block is allocated before // the def block (removing the vreg uses). mayLiveIn(Reg); assert(!MO.isInternalRead() && "Bundles not supported"); assert(MO.readsReg() && "reading use"); useVirtReg(MI, I, Reg); } // Allocate undef operands. This is a separate step because in a situation // like ` = OP undef %X, %X` both operands need the same register assign // so we should perform the normal assignment first. if (HasUndefUse) { for (MachineOperand &MO : MI.uses()) { if (!MO.isReg() || !MO.isUse()) continue; Register Reg = MO.getReg(); if (!Reg.isVirtual()) continue; assert(MO.isUndef() && "Should only have undef virtreg uses left"); allocVirtRegUndef(MO); } } // Free early clobbers. if (HasEarlyClobber) { for (MachineOperand &MO : llvm::reverse(MI.operands())) { if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber()) continue; // subreg defs don't free the full register. We left the subreg number // around as a marker in setPhysReg() to recognize this case here. if (MO.getSubReg() != 0) { MO.setSubReg(0); continue; } Register Reg = MO.getReg(); if (!Reg) continue; assert(Reg.isPhysical() && "should have register assigned"); // We sometimes get odd situations like: // early-clobber %x0 = INSTRUCTION %x0 // which is semantically questionable as the early-clobber should // apply before the use. But in practice we consider the use to // happen before the early clobber now. Don't free the early clobber // register in this case. if (MI.readsRegister(Reg, TRI)) continue; freePhysReg(Reg); } } LLVM_DEBUG(dbgs() << "<< " << MI); if (MI.isCopy() && MI.getOperand(0).getReg() == MI.getOperand(1).getReg() && MI.getNumOperands() == 2) { LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n"); Coalesced.push_back(&MI); } } void RegAllocFast::handleDebugValue(MachineInstr &MI) { // Ignore DBG_VALUEs that aren't based on virtual registers. These are // mostly constants and frame indices. for (Register Reg : MI.getUsedDebugRegs()) { if (!Register::isVirtualRegister(Reg)) continue; // Already spilled to a stackslot? int SS = StackSlotForVirtReg[Reg]; if (SS != -1) { // Modify DBG_VALUE now that the value is in a spill slot. updateDbgValueForSpill(MI, SS, Reg); LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI); continue; } // See if this virtual register has already been allocated to a physical // register or spilled to a stack slot. LiveRegMap::iterator LRI = findLiveVirtReg(Reg); SmallVector DbgOps; for (MachineOperand &Op : MI.getDebugOperandsForReg(Reg)) DbgOps.push_back(&Op); if (LRI != LiveVirtRegs.end() && LRI->PhysReg) { // Update every use of Reg within MI. for (auto &RegMO : DbgOps) setPhysReg(MI, *RegMO, LRI->PhysReg); } else { DanglingDbgValues[Reg].push_back(&MI); } // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so // that future spills of Reg will have DBG_VALUEs. LiveDbgValueMap[Reg].append(DbgOps.begin(), DbgOps.end()); } } void RegAllocFast::handleBundle(MachineInstr &MI) { MachineBasicBlock::instr_iterator BundledMI = MI.getIterator(); ++BundledMI; while (BundledMI->isBundledWithPred()) { for (MachineOperand &MO : BundledMI->operands()) { if (!MO.isReg()) continue; Register Reg = MO.getReg(); if (!Reg.isVirtual()) continue; DenseMap::iterator DI; DI = BundleVirtRegsMap.find(Reg); assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register"); setPhysReg(MI, MO, DI->second); } ++BundledMI; } } void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) { this->MBB = &MBB; LLVM_DEBUG(dbgs() << "\nAllocating " << MBB); RegUnitStates.assign(TRI->getNumRegUnits(), regFree); assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?"); for (const auto &LiveReg : MBB.liveouts()) setPhysRegState(LiveReg.PhysReg, regPreAssigned); Coalesced.clear(); // Traverse block in reverse order allocating instructions one by one. for (MachineInstr &MI : reverse(MBB)) { LLVM_DEBUG( dbgs() << "\n>> " << MI << "Regs:"; dumpState() ); // Special handling for debug values. Note that they are not allowed to // affect codegen of the other instructions in any way. if (MI.isDebugValue()) { handleDebugValue(MI); continue; } allocateInstruction(MI); // Once BUNDLE header is assigned registers, same assignments need to be // done for bundled MIs. if (MI.getOpcode() == TargetOpcode::BUNDLE) { handleBundle(MI); } } LLVM_DEBUG( dbgs() << "Begin Regs:"; dumpState() ); // Spill all physical registers holding virtual registers now. LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n"); reloadAtBegin(MBB); // Erase all the coalesced copies. We are delaying it until now because // LiveVirtRegs might refer to the instrs. for (MachineInstr *MI : Coalesced) MBB.erase(MI); NumCoalesced += Coalesced.size(); for (auto &UDBGPair : DanglingDbgValues) { for (MachineInstr *DbgValue : UDBGPair.second) { assert(DbgValue->isDebugValue() && "expected DBG_VALUE"); // Nothing to do if the vreg was spilled in the meantime. if (!DbgValue->hasDebugOperandForReg(UDBGPair.first)) continue; LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue << '\n'); DbgValue->setDebugValueUndef(); } } DanglingDbgValues.clear(); LLVM_DEBUG(MBB.dump()); } bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) { LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n" << "********** Function: " << MF.getName() << '\n'); MRI = &MF.getRegInfo(); const TargetSubtargetInfo &STI = MF.getSubtarget(); TRI = STI.getRegisterInfo(); TII = STI.getInstrInfo(); MFI = &MF.getFrameInfo(); MRI->freezeReservedRegs(MF); RegClassInfo.runOnMachineFunction(MF); unsigned NumRegUnits = TRI->getNumRegUnits(); UsedInInstr.clear(); UsedInInstr.setUniverse(NumRegUnits); PhysRegUses.clear(); PhysRegUses.setUniverse(NumRegUnits); // initialize the virtual->physical register map to have a 'null' // mapping for all virtual registers unsigned NumVirtRegs = MRI->getNumVirtRegs(); StackSlotForVirtReg.resize(NumVirtRegs); LiveVirtRegs.setUniverse(NumVirtRegs); MayLiveAcrossBlocks.clear(); MayLiveAcrossBlocks.resize(NumVirtRegs); // Loop over all of the basic blocks, eliminating virtual register references for (MachineBasicBlock &MBB : MF) allocateBasicBlock(MBB); if (ClearVirtRegs) { // All machine operands and other references to virtual registers have been // replaced. Remove the virtual registers. MRI->clearVirtRegs(); } StackSlotForVirtReg.clear(); LiveDbgValueMap.clear(); return true; } FunctionPass *llvm::createFastRegisterAllocator() { return new RegAllocFast(); } FunctionPass *llvm::createFastRegisterAllocator(RegClassFilterFunc Ftor, bool ClearVirtRegs) { return new RegAllocFast(Ftor, ClearVirtRegs); } diff --git a/llvm/lib/CodeGen/TypePromotion.cpp b/llvm/lib/CodeGen/TypePromotion.cpp index a63118067139..36e3c1245f1c 100644 --- a/llvm/lib/CodeGen/TypePromotion.cpp +++ b/llvm/lib/CodeGen/TypePromotion.cpp @@ -1,960 +1,956 @@ //===----- TypePromotion.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 // //===----------------------------------------------------------------------===// // /// \file /// This is an opcode based type promotion pass for small types that would /// otherwise be promoted during legalisation. This works around the limitations /// of selection dag for cyclic regions. The search begins from icmp /// instructions operands where a tree, consisting of non-wrapping or safe /// wrapping instructions, is built, checked and promoted if possible. /// //===----------------------------------------------------------------------===// #include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/TargetLowering.h" #include "llvm/CodeGen/TargetPassConfig.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constants.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetMachine.h" #define DEBUG_TYPE "type-promotion" #define PASS_NAME "Type Promotion" using namespace llvm; static cl::opt DisablePromotion("disable-type-promotion", cl::Hidden, cl::init(false), cl::desc("Disable type promotion pass")); // The goal of this pass is to enable more efficient code generation for // operations on narrow types (i.e. types with < 32-bits) and this is a // motivating IR code example: // // define hidden i32 @cmp(i8 zeroext) { // %2 = add i8 %0, -49 // %3 = icmp ult i8 %2, 3 // .. // } // // The issue here is that i8 is type-legalized to i32 because i8 is not a // legal type. Thus, arithmetic is done in integer-precision, but then the // byte value is masked out as follows: // // t19: i32 = add t4, Constant:i32<-49> // t24: i32 = and t19, Constant:i32<255> // // Consequently, we generate code like this: // // subs r0, #49 // uxtb r1, r0 // cmp r1, #3 // // This shows that masking out the byte value results in generation of // the UXTB instruction. This is not optimal as r0 already contains the byte // value we need, and so instead we can just generate: // // sub.w r1, r0, #49 // cmp r1, #3 // // We achieve this by type promoting the IR to i32 like so for this example: // // define i32 @cmp(i8 zeroext %c) { // %0 = zext i8 %c to i32 // %c.off = add i32 %0, -49 // %1 = icmp ult i32 %c.off, 3 // .. // } // // For this to be valid and legal, we need to prove that the i32 add is // producing the same value as the i8 addition, and that e.g. no overflow // happens. // // A brief sketch of the algorithm and some terminology. // We pattern match interesting IR patterns: // - which have "sources": instructions producing narrow values (i8, i16), and // - they have "sinks": instructions consuming these narrow values. // // We collect all instruction connecting sources and sinks in a worklist, so // that we can mutate these instruction and perform type promotion when it is // legal to do so. namespace { class IRPromoter { LLVMContext &Ctx; unsigned PromotedWidth = 0; SetVector &Visited; SetVector &Sources; SetVector &Sinks; SmallPtrSetImpl &SafeWrap; IntegerType *ExtTy = nullptr; SmallPtrSet NewInsts; SmallPtrSet InstsToRemove; DenseMap> TruncTysMap; SmallPtrSet Promoted; void ReplaceAllUsersOfWith(Value *From, Value *To); void ExtendSources(); void ConvertTruncs(); void PromoteTree(); void TruncateSinks(); void Cleanup(); public: IRPromoter(LLVMContext &C, unsigned Width, SetVector &visited, SetVector &sources, SetVector &sinks, SmallPtrSetImpl &wrap) : Ctx(C), PromotedWidth(Width), Visited(visited), Sources(sources), Sinks(sinks), SafeWrap(wrap) { ExtTy = IntegerType::get(Ctx, PromotedWidth); } void Mutate(); }; class TypePromotion : public FunctionPass { unsigned TypeSize = 0; LLVMContext *Ctx = nullptr; unsigned RegisterBitWidth = 0; SmallPtrSet AllVisited; SmallPtrSet SafeToPromote; SmallPtrSet SafeWrap; // Does V have the same size result type as TypeSize. bool EqualTypeSize(Value *V); // Does V have the same size, or narrower, result type as TypeSize. bool LessOrEqualTypeSize(Value *V); // Does V have a result type that is wider than TypeSize. bool GreaterThanTypeSize(Value *V); // Does V have a result type that is narrower than TypeSize. bool LessThanTypeSize(Value *V); // Should V be a leaf in the promote tree? bool isSource(Value *V); // Should V be a root in the promotion tree? bool isSink(Value *V); // Should we change the result type of V? It will result in the users of V // being visited. bool shouldPromote(Value *V); // Is I an add or a sub, which isn't marked as nuw, but where a wrapping // result won't affect the computation? bool isSafeWrap(Instruction *I); // Can V have its integer type promoted, or can the type be ignored. bool isSupportedType(Value *V); // Is V an instruction with a supported opcode or another value that we can // handle, such as constants and basic blocks. bool isSupportedValue(Value *V); // Is V an instruction thats result can trivially promoted, or has safe // wrapping. bool isLegalToPromote(Value *V); bool TryToPromote(Value *V, unsigned PromotedWidth); public: static char ID; TypePromotion() : FunctionPass(ID) {} void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); AU.setPreservesCFG(); } StringRef getPassName() const override { return PASS_NAME; } bool runOnFunction(Function &F) override; }; } // namespace static bool GenerateSignBits(Instruction *I) { unsigned Opc = I->getOpcode(); return Opc == Instruction::AShr || Opc == Instruction::SDiv || Opc == Instruction::SRem || Opc == Instruction::SExt; } bool TypePromotion::EqualTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() == TypeSize; } bool TypePromotion::LessOrEqualTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() <= TypeSize; } bool TypePromotion::GreaterThanTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() > TypeSize; } bool TypePromotion::LessThanTypeSize(Value *V) { return V->getType()->getScalarSizeInBits() < TypeSize; } /// Return true if the given value is a source in the use-def chain, producing /// a narrow 'TypeSize' value. These values will be zext to start the promotion /// of the tree to i32. We guarantee that these won't populate the upper bits /// of the register. ZExt on the loads will be free, and the same for call /// return values because we only accept ones that guarantee a zeroext ret val. /// Many arguments will have the zeroext attribute too, so those would be free /// too. bool TypePromotion::isSource(Value *V) { if (!isa(V->getType())) return false; // TODO Allow zext to be sources. if (isa(V)) return true; else if (isa(V)) return true; else if (isa(V)) return true; else if (auto *Call = dyn_cast(V)) return Call->hasRetAttr(Attribute::AttrKind::ZExt); else if (auto *Trunc = dyn_cast(V)) return EqualTypeSize(Trunc); return false; } /// Return true if V will require any promoted values to be truncated for the /// the IR to remain valid. We can't mutate the value type of these /// instructions. bool TypePromotion::isSink(Value *V) { // TODO The truncate also isn't actually necessary because we would already // proved that the data value is kept within the range of the original data // type. We currently remove any truncs inserted for handling zext sinks. // Sinks are: // - points where the value in the register is being observed, such as an // icmp, switch or store. // - points where value types have to match, such as calls and returns. // - zext are included to ease the transformation and are generally removed // later on. if (auto *Store = dyn_cast(V)) return LessOrEqualTypeSize(Store->getValueOperand()); if (auto *Return = dyn_cast(V)) return LessOrEqualTypeSize(Return->getReturnValue()); if (auto *ZExt = dyn_cast(V)) return GreaterThanTypeSize(ZExt); if (auto *Switch = dyn_cast(V)) return LessThanTypeSize(Switch->getCondition()); if (auto *ICmp = dyn_cast(V)) return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0)); return isa(V); } /// Return whether this instruction can safely wrap. bool TypePromotion::isSafeWrap(Instruction *I) { // We can support a potentially wrapping instruction (I) if: // - It is only used by an unsigned icmp. // - The icmp uses a constant. // - The wrapping value (I) is decreasing, i.e would underflow - wrapping // around zero to become a larger number than before. // - The wrapping instruction (I) also uses a constant. // // We can then use the two constants to calculate whether the result would // wrap in respect to itself in the original bitwidth. If it doesn't wrap, // just underflows the range, the icmp would give the same result whether the // result has been truncated or not. We calculate this by: // - Zero extending both constants, if needed, to RegisterBitWidth. // - Take the absolute value of I's constant, adding this to the icmp const. // - Check that this value is not out of range for small type. If it is, it // means that it has underflowed enough to wrap around the icmp constant. // // For example: // // %sub = sub i8 %a, 2 // %cmp = icmp ule i8 %sub, 254 // // If %a = 0, %sub = -2 == FE == 254 // But if this is evalulated as a i32 // %sub = -2 == FF FF FF FE == 4294967294 // So the unsigned compares (i8 and i32) would not yield the same result. // // Another way to look at it is: // %a - 2 <= 254 // %a + 2 <= 254 + 2 // %a <= 256 // And we can't represent 256 in the i8 format, so we don't support it. // // Whereas: // // %sub i8 %a, 1 // %cmp = icmp ule i8 %sub, 254 // // If %a = 0, %sub = -1 == FF == 255 // As i32: // %sub = -1 == FF FF FF FF == 4294967295 // // In this case, the unsigned compare results would be the same and this // would also be true for ult, uge and ugt: // - (255 < 254) == (0xFFFFFFFF < 254) == false // - (255 <= 254) == (0xFFFFFFFF <= 254) == false // - (255 > 254) == (0xFFFFFFFF > 254) == true // - (255 >= 254) == (0xFFFFFFFF >= 254) == true // // To demonstrate why we can't handle increasing values: // // %add = add i8 %a, 2 // %cmp = icmp ult i8 %add, 127 // // If %a = 254, %add = 256 == (i8 1) // As i32: // %add = 256 // // (1 < 127) != (256 < 127) unsigned Opc = I->getOpcode(); if (Opc != Instruction::Add && Opc != Instruction::Sub) return false; if (!I->hasOneUse() || !isa(*I->user_begin()) || !isa(I->getOperand(1))) return false; // Don't support an icmp that deals with sign bits. auto *CI = cast(*I->user_begin()); if (CI->isSigned() || CI->isEquality()) return false; ConstantInt *ICmpConstant = nullptr; if (auto *Const = dyn_cast(CI->getOperand(0))) ICmpConstant = Const; else if (auto *Const = dyn_cast(CI->getOperand(1))) ICmpConstant = Const; else return false; const APInt &ICmpConst = ICmpConstant->getValue(); APInt OverflowConst = cast(I->getOperand(1))->getValue(); if (Opc == Instruction::Sub) OverflowConst = -OverflowConst; if (!OverflowConst.isNonPositive()) return false; // Using C1 = OverflowConst and C2 = ICmpConst, we can either prove that: // zext(x) + sext(C1) s C2 // zext(x) + sext(C1) (V->getType()) || isSink(V)) return false; if (isSource(V)) return true; auto *I = dyn_cast(V); if (!I) return false; if (isa(I)) return false; return true; } /// Return whether we can safely mutate V's type to ExtTy without having to be /// concerned with zero extending or truncation. static bool isPromotedResultSafe(Instruction *I) { if (GenerateSignBits(I)) return false; if (!isa(I)) return true; return I->hasNoUnsignedWrap(); } void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) { SmallVector Users; Instruction *InstTo = dyn_cast(To); bool ReplacedAll = true; LLVM_DEBUG(dbgs() << "IR Promotion: Replacing " << *From << " with " << *To << "\n"); for (Use &U : From->uses()) { auto *User = cast(U.getUser()); if (InstTo && User->isIdenticalTo(InstTo)) { ReplacedAll = false; continue; } Users.push_back(User); } for (auto *U : Users) U->replaceUsesOfWith(From, To); if (ReplacedAll) if (auto *I = dyn_cast(From)) InstsToRemove.insert(I); } void IRPromoter::ExtendSources() { IRBuilder<> Builder{Ctx}; auto InsertZExt = [&](Value *V, Instruction *InsertPt) { assert(V->getType() != ExtTy && "zext already extends to i32"); LLVM_DEBUG(dbgs() << "IR Promotion: Inserting ZExt for " << *V << "\n"); Builder.SetInsertPoint(InsertPt); if (auto *I = dyn_cast(V)) Builder.SetCurrentDebugLocation(I->getDebugLoc()); Value *ZExt = Builder.CreateZExt(V, ExtTy); if (auto *I = dyn_cast(ZExt)) { if (isa(V)) I->moveBefore(InsertPt); else I->moveAfter(InsertPt); NewInsts.insert(I); } ReplaceAllUsersOfWith(V, ZExt); }; // Now, insert extending instructions between the sources and their users. LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n"); for (auto *V : Sources) { LLVM_DEBUG(dbgs() << " - " << *V << "\n"); if (auto *I = dyn_cast(V)) InsertZExt(I, I); else if (auto *Arg = dyn_cast(V)) { BasicBlock &BB = Arg->getParent()->front(); InsertZExt(Arg, &*BB.getFirstInsertionPt()); } else { llvm_unreachable("unhandled source that needs extending"); } Promoted.insert(V); } } void IRPromoter::PromoteTree() { LLVM_DEBUG(dbgs() << "IR Promotion: Mutating the tree..\n"); // Mutate the types of the instructions within the tree. Here we handle // constant operands. for (auto *V : Visited) { if (Sources.count(V)) continue; auto *I = cast(V); if (Sinks.count(I)) continue; for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) { Value *Op = I->getOperand(i); if ((Op->getType() == ExtTy) || !isa(Op->getType())) continue; if (auto *Const = dyn_cast(Op)) { // For subtract, we don't need to sext the constant. We only put it in // SafeWrap because SafeWrap.size() is used elsewhere. // For cmp, we need to sign extend a constant appearing in either // operand. For add, we should only sign extend the RHS. Constant *NewConst = (SafeWrap.contains(I) && (I->getOpcode() == Instruction::ICmp || i == 1) && I->getOpcode() != Instruction::Sub) ? ConstantExpr::getSExt(Const, ExtTy) : ConstantExpr::getZExt(Const, ExtTy); I->setOperand(i, NewConst); } else if (isa(Op)) I->setOperand(i, ConstantInt::get(ExtTy, 0)); } // Mutate the result type, unless this is an icmp or switch. if (!isa(I) && !isa(I)) { I->mutateType(ExtTy); Promoted.insert(I); } } } void IRPromoter::TruncateSinks() { LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n"); IRBuilder<> Builder{Ctx}; auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction * { if (!isa(V) || !isa(V->getType())) return nullptr; if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V)) return nullptr; LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for " << *V << "\n"); Builder.SetInsertPoint(cast(V)); auto *Trunc = dyn_cast(Builder.CreateTrunc(V, TruncTy)); if (Trunc) NewInsts.insert(Trunc); return Trunc; }; // Fix up any stores or returns that use the results of the promoted // chain. for (auto *I : Sinks) { LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n"); // Handle calls separately as we need to iterate over arg operands. if (auto *Call = dyn_cast(I)) { for (unsigned i = 0; i < Call->arg_size(); ++i) { Value *Arg = Call->getArgOperand(i); Type *Ty = TruncTysMap[Call][i]; if (Instruction *Trunc = InsertTrunc(Arg, Ty)) { Trunc->moveBefore(Call); Call->setArgOperand(i, Trunc); } } continue; } // Special case switches because we need to truncate the condition. if (auto *Switch = dyn_cast(I)) { Type *Ty = TruncTysMap[Switch][0]; if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) { Trunc->moveBefore(Switch); Switch->setCondition(Trunc); } continue; } // Don't insert a trunc for a zext which can still legally promote. if (auto ZExt = dyn_cast(I)) if (ZExt->getType()->getScalarSizeInBits() > PromotedWidth) continue; // Now handle the others. for (unsigned i = 0; i < I->getNumOperands(); ++i) { Type *Ty = TruncTysMap[I][i]; if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) { Trunc->moveBefore(I); I->setOperand(i, Trunc); } } } } void IRPromoter::Cleanup() { LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n"); // Some zexts will now have become redundant, along with their trunc // operands, so remove them. - // Some zexts need to be replaced with truncate if src bitwidth is larger. for (auto *V : Visited) { if (!isa(V)) continue; auto ZExt = cast(V); if (ZExt->getDestTy() != ExtTy) continue; Value *Src = ZExt->getOperand(0); if (ZExt->getSrcTy() == ZExt->getDestTy()) { LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt << "\n"); ReplaceAllUsersOfWith(ZExt, Src); continue; - } else if (ZExt->getSrcTy()->getScalarSizeInBits() > PromotedWidth) { - IRBuilder<> Builder{ZExt}; - Value *Trunc = Builder.CreateTrunc(Src, ZExt->getDestTy()); - ReplaceAllUsersOfWith(ZExt, Trunc); - continue; } // We've inserted a trunc for a zext sink, but we already know that the // input is in range, negating the need for the trunc. if (NewInsts.count(Src) && isa(Src)) { auto *Trunc = cast(Src); assert(Trunc->getOperand(0)->getType() == ExtTy && "expected inserted trunc to be operating on i32"); ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0)); } } for (auto *I : InstsToRemove) { LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n"); I->dropAllReferences(); I->eraseFromParent(); } } void IRPromoter::ConvertTruncs() { LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n"); IRBuilder<> Builder{Ctx}; for (auto *V : Visited) { if (!isa(V) || Sources.count(V)) continue; auto *Trunc = cast(V); Builder.SetInsertPoint(Trunc); IntegerType *SrcTy = cast(Trunc->getOperand(0)->getType()); IntegerType *DestTy = cast(TruncTysMap[Trunc][0]); unsigned NumBits = DestTy->getScalarSizeInBits(); ConstantInt *Mask = ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue()); Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask); + if (SrcTy != ExtTy) + Masked = Builder.CreateTrunc(Masked, ExtTy); if (auto *I = dyn_cast(Masked)) NewInsts.insert(I); ReplaceAllUsersOfWith(Trunc, Masked); } } void IRPromoter::Mutate() { LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains to " << PromotedWidth << "-bits\n"); // Cache original types of the values that will likely need truncating for (auto *I : Sinks) { if (auto *Call = dyn_cast(I)) { for (Value *Arg : Call->args()) TruncTysMap[Call].push_back(Arg->getType()); } else if (auto *Switch = dyn_cast(I)) TruncTysMap[I].push_back(Switch->getCondition()->getType()); else { for (unsigned i = 0; i < I->getNumOperands(); ++i) TruncTysMap[I].push_back(I->getOperand(i)->getType()); } } for (auto *V : Visited) { if (!isa(V) || Sources.count(V)) continue; auto *Trunc = cast(V); TruncTysMap[Trunc].push_back(Trunc->getDestTy()); } // Insert zext instructions between sources and their users. ExtendSources(); // Promote visited instructions, mutating their types in place. PromoteTree(); // Convert any truncs, that aren't sources, into AND masks. ConvertTruncs(); // Insert trunc instructions for use by calls, stores etc... TruncateSinks(); // Finally, remove unecessary zexts and truncs, delete old instructions and // clear the data structures. Cleanup(); LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n"); } /// We disallow booleans to make life easier when dealing with icmps but allow /// any other integer that fits in a scalar register. Void types are accepted /// so we can handle switches. bool TypePromotion::isSupportedType(Value *V) { Type *Ty = V->getType(); // Allow voids and pointers, these won't be promoted. if (Ty->isVoidTy() || Ty->isPointerTy()) return true; if (!isa(Ty) || cast(Ty)->getBitWidth() == 1 || cast(Ty)->getBitWidth() > RegisterBitWidth) return false; return LessOrEqualTypeSize(V); } /// We accept most instructions, as well as Arguments and ConstantInsts. We /// Disallow casts other than zext and truncs and only allow calls if their /// return value is zeroext. We don't allow opcodes that can introduce sign /// bits. bool TypePromotion::isSupportedValue(Value *V) { if (auto *I = dyn_cast(V)) { switch (I->getOpcode()) { default: return isa(I) && isSupportedType(I) && !GenerateSignBits(I); case Instruction::GetElementPtr: case Instruction::Store: case Instruction::Br: case Instruction::Switch: return true; case Instruction::PHI: case Instruction::Select: case Instruction::Ret: case Instruction::Load: case Instruction::Trunc: case Instruction::BitCast: return isSupportedType(I); case Instruction::ZExt: return isSupportedType(I->getOperand(0)); case Instruction::ICmp: // Now that we allow small types than TypeSize, only allow icmp of // TypeSize because they will require a trunc to be legalised. // TODO: Allow icmp of smaller types, and calculate at the end // whether the transform would be beneficial. if (isa(I->getOperand(0)->getType())) return true; return EqualTypeSize(I->getOperand(0)); case Instruction::Call: { // Special cases for calls as we need to check for zeroext // TODO We should accept calls even if they don't have zeroext, as they // can still be sinks. auto *Call = cast(I); return isSupportedType(Call) && Call->hasRetAttr(Attribute::AttrKind::ZExt); } } } else if (isa(V) && !isa(V)) { return isSupportedType(V); } else if (isa(V)) return isSupportedType(V); return isa(V); } /// Check that the type of V would be promoted and that the original type is /// smaller than the targeted promoted type. Check that we're not trying to /// promote something larger than our base 'TypeSize' type. bool TypePromotion::isLegalToPromote(Value *V) { auto *I = dyn_cast(V); if (!I) return true; if (SafeToPromote.count(I)) return true; if (isPromotedResultSafe(I) || isSafeWrap(I)) { SafeToPromote.insert(I); return true; } return false; } bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) { Type *OrigTy = V->getType(); TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedSize(); SafeToPromote.clear(); SafeWrap.clear(); if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V)) return false; LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from " << TypeSize << " bits to " << PromotedWidth << "\n"); SetVector WorkList; SetVector Sources; SetVector Sinks; SetVector CurrentVisited; WorkList.insert(V); // Return true if V was added to the worklist as a supported instruction, // if it was already visited, or if we don't need to explore it (e.g. // pointer values and GEPs), and false otherwise. auto AddLegalInst = [&](Value *V) { if (CurrentVisited.count(V)) return true; // Ignore GEPs because they don't need promoting and the constant indices // will prevent the transformation. if (isa(V)) return true; if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) { LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n"); return false; } WorkList.insert(V); return true; }; // Iterate through, and add to, a tree of operands and users in the use-def. while (!WorkList.empty()) { Value *V = WorkList.pop_back_val(); if (CurrentVisited.count(V)) continue; // Ignore non-instructions, other than arguments. if (!isa(V) && !isSource(V)) continue; // If we've already visited this value from somewhere, bail now because // the tree has already been explored. // TODO: This could limit the transform, ie if we try to promote something // from an i8 and fail first, before trying an i16. if (AllVisited.count(V)) return false; CurrentVisited.insert(V); AllVisited.insert(V); // Calls can be both sources and sinks. if (isSink(V)) Sinks.insert(cast(V)); if (isSource(V)) Sources.insert(V); if (!isSink(V) && !isSource(V)) { if (auto *I = dyn_cast(V)) { // Visit operands of any instruction visited. for (auto &U : I->operands()) { if (!AddLegalInst(U)) return false; } } } // Don't visit users of a node which isn't going to be mutated unless its a // source. if (isSource(V) || shouldPromote(V)) { for (Use &U : V->uses()) { if (!AddLegalInst(U.getUser())) return false; } } } LLVM_DEBUG({ dbgs() << "IR Promotion: Visited nodes:\n"; for (auto *I : CurrentVisited) I->dump(); }); unsigned ToPromote = 0; unsigned NonFreeArgs = 0; SmallPtrSet Blocks; for (auto *V : CurrentVisited) { if (auto *I = dyn_cast(V)) Blocks.insert(I->getParent()); if (Sources.count(V)) { if (auto *Arg = dyn_cast(V)) if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr()) ++NonFreeArgs; continue; } if (Sinks.count(cast(V))) continue; ++ToPromote; } // DAG optimizations should be able to handle these cases better, especially // for function arguments. if (ToPromote < 2 || (Blocks.size() == 1 && (NonFreeArgs > SafeWrap.size()))) return false; IRPromoter Promoter(*Ctx, PromotedWidth, CurrentVisited, Sources, Sinks, SafeWrap); Promoter.Mutate(); return true; } bool TypePromotion::runOnFunction(Function &F) { if (skipFunction(F) || DisablePromotion) return false; LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n"); auto *TPC = getAnalysisIfAvailable(); if (!TPC) return false; AllVisited.clear(); SafeToPromote.clear(); SafeWrap.clear(); bool MadeChange = false; const DataLayout &DL = F.getParent()->getDataLayout(); const TargetMachine &TM = TPC->getTM(); const TargetSubtargetInfo *SubtargetInfo = TM.getSubtargetImpl(F); const TargetLowering *TLI = SubtargetInfo->getTargetLowering(); const TargetTransformInfo &TII = getAnalysis().getTTI(F); RegisterBitWidth = TII.getRegisterBitWidth(TargetTransformInfo::RGK_Scalar).getFixedSize(); Ctx = &F.getParent()->getContext(); // Search up from icmps to try to promote their operands. for (BasicBlock &BB : F) { for (Instruction &I : BB) { if (AllVisited.count(&I)) continue; if (!isa(&I)) continue; auto *ICmp = cast(&I); // Skip signed or pointer compares if (ICmp->isSigned() || !isa(ICmp->getOperand(0)->getType())) continue; LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n"); for (auto &Op : ICmp->operands()) { if (auto *I = dyn_cast(Op)) { EVT SrcVT = TLI->getValueType(DL, I->getType()); if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT())) break; if (TLI->getTypeAction(*Ctx, SrcVT) != TargetLowering::TypePromoteInteger) break; EVT PromotedVT = TLI->getTypeToTransformTo(*Ctx, SrcVT); if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) { LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register " << "for promoted type\n"); break; } MadeChange |= TryToPromote(I, PromotedVT.getFixedSizeInBits()); break; } } } } AllVisited.clear(); SafeToPromote.clear(); SafeWrap.clear(); return MadeChange; } INITIALIZE_PASS_BEGIN(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false) INITIALIZE_PASS_END(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false) char TypePromotion::ID = 0; FunctionPass *llvm::createTypePromotionPass() { return new TypePromotion(); }