Vendor import of llvm-project branch release/16.x llvmorg-16.0.1-0-gcd89023f7979 (aka 16.0.1 release).vendor/llvm-project/llvmorg-16.0.1-0-gcd89023f7979

26 files changed, 578 insertions, 671 deletions

diff --git a/clang/include/clang/Format/Format.h b/clang/include/clang/Format/Format.h
index 72efd3be1cc7..7a313460d888 100644
--- a/clang/include/clang/Format/Format.h
+++ b/clang/include/clang/Format/Format.h
@@ -2500,6 +2500,10 @@ struct FormatStyle {
   ///     Decimal: 3
   ///     Hex: -1
   /// \endcode
+  ///
+  /// You can also specify a minimum number of digits (``BinaryMinDigits``,
+  /// ``DecimalMinDigits``, and ``HexMinDigits``) the integer literal must
+  /// have in order for the separators to be inserted.
   struct IntegerLiteralSeparatorStyle {
     /// Format separators in binary literals.
     /// \code{.text}
@@ -2509,6 +2513,14 @@ struct FormatStyle {
     ///   /*  4: */ b = 0b1001'1110'1101;
     /// \endcode
     int8_t Binary;
+    /// Format separators in binary literals with a minimum number of digits.
+    /// \code{.text}
+    ///   // Binary: 3
+    ///   // BinaryMinDigits: 7
+    ///   b1 = 0b101101;
+    ///   b2 = 0b1'101'101;
+    /// \endcode
+    int8_t BinaryMinDigits;
     /// Format separators in decimal literals.
     /// \code{.text}
     ///   /* -1: */ d = 18446744073709550592ull;
@@ -2516,6 +2528,14 @@ struct FormatStyle {
     ///   /*  3: */ d = 18'446'744'073'709'550'592ull;
     /// \endcode
     int8_t Decimal;
+    /// Format separators in decimal literals with a minimum number of digits.
+    /// \code{.text}
+    ///   // Decimal: 3
+    ///   // DecimalMinDigits: 5
+    ///   d1 = 2023;
+    ///   d2 = 10'000;
+    /// \endcode
+    int8_t DecimalMinDigits;
     /// Format separators in hexadecimal literals.
     /// \code{.text}
     ///   /* -1: */ h = 0xDEADBEEFDEADBEEFuz;
@@ -2523,6 +2543,20 @@ struct FormatStyle {
     ///   /*  2: */ h = 0xDE'AD'BE'EF'DE'AD'BE'EFuz;
     /// \endcode
     int8_t Hex;
+    /// Format separators in hexadecimal literals with a minimum number of
+    /// digits.
+    /// \code{.text}
+    ///   // Hex: 2
+    ///   // HexMinDigits: 6
+    ///   h1 = 0xABCDE;
+    ///   h2 = 0xAB'CD'EF;
+    /// \endcode
+    int8_t HexMinDigits;
+    bool operator==(const IntegerLiteralSeparatorStyle &R) const {
+      return Binary == R.Binary && BinaryMinDigits == R.BinaryMinDigits &&
+             Decimal == R.Decimal && DecimalMinDigits == R.DecimalMinDigits &&
+             Hex == R.Hex && HexMinDigits == R.HexMinDigits;
+    }
   };
 
   /// Format integer literal separators (``'`` for C++ and ``_`` for C#, Java,
@@ -4212,10 +4246,7 @@ struct FormatStyle {
            IndentWrappedFunctionNames == R.IndentWrappedFunctionNames &&
            InsertBraces == R.InsertBraces &&
            InsertNewlineAtEOF == R.InsertNewlineAtEOF &&
-           IntegerLiteralSeparator.Binary == R.IntegerLiteralSeparator.Binary &&
-           IntegerLiteralSeparator.Decimal ==
-               R.IntegerLiteralSeparator.Decimal &&
-           IntegerLiteralSeparator.Hex == R.IntegerLiteralSeparator.Hex &&
+           IntegerLiteralSeparator == R.IntegerLiteralSeparator &&
            JavaImportGroups == R.JavaImportGroups &&
            JavaScriptQuotes == R.JavaScriptQuotes &&
            JavaScriptWrapImports == R.JavaScriptWrapImports &&
diff --git a/clang/lib/Driver/ToolChains/MinGW.cpp b/clang/lib/Driver/ToolChains/MinGW.cpp
index 908484fcc0b8..bac486bab885 100644
--- a/clang/lib/Driver/ToolChains/MinGW.cpp
+++ b/clang/lib/Driver/ToolChains/MinGW.cpp
@@ -200,6 +200,16 @@ void tools::MinGW::Linker::ConstructJob(Compilation &C, const JobAction &JA,
   Args.AddAllArgs(CmdArgs, options::OPT_u_Group);
   Args.AddLastArg(CmdArgs, options::OPT_Z_Flag);
 
+  // Add asan_dynamic as the first import lib before other libs. This allows
+  // asan to be initialized as early as possible to increase its instrumentation
+  // coverage to include other user DLLs which has not been built with asan.
+  if (Sanitize.needsAsanRt() && !Args.hasArg(options::OPT_nostdlib) &&
+      !Args.hasArg(options::OPT_nodefaultlibs)) {
+    // MinGW always links against a shared MSVCRT.
+    CmdArgs.push_back(
+        TC.getCompilerRTArgString(Args, "asan_dynamic", ToolChain::FT_Shared));
+  }
+
   if (!Args.hasArg(options::OPT_nostdlib, options::OPT_nostartfiles)) {
     if (Args.hasArg(options::OPT_shared) || Args.hasArg(options::OPT_mdll)) {
       CmdArgs.push_back(Args.MakeArgString(TC.GetFilePath("dllcrt2.o")));
diff --git a/clang/lib/Format/Format.cpp b/clang/lib/Format/Format.cpp
index f37c3f983635..0d3fde90ab38 100644
--- a/clang/lib/Format/Format.cpp
+++ b/clang/lib/Format/Format.cpp
@@ -348,8 +348,11 @@ struct ScalarEnumerationTraits<FormatStyle::IndentExternBlockStyle> {
 template <> struct MappingTraits<FormatStyle::IntegerLiteralSeparatorStyle> {
   static void mapping(IO &IO, FormatStyle::IntegerLiteralSeparatorStyle &Base) {
     IO.mapOptional("Binary", Base.Binary);
+    IO.mapOptional("BinaryMinDigits", Base.BinaryMinDigits);
     IO.mapOptional("Decimal", Base.Decimal);
+    IO.mapOptional("DecimalMinDigits", Base.DecimalMinDigits);
     IO.mapOptional("Hex", Base.Hex);
+    IO.mapOptional("HexMinDigits", Base.HexMinDigits);
   }
 };
 
@@ -1392,7 +1395,10 @@ FormatStyle getLLVMStyle(FormatStyle::LanguageKind Language) {
   LLVMStyle.InsertBraces = false;
   LLVMStyle.InsertNewlineAtEOF = false;
   LLVMStyle.InsertTrailingCommas = FormatStyle::TCS_None;
-  LLVMStyle.IntegerLiteralSeparator = {/*Binary=*/0, /*Decimal=*/0, /*Hex=*/0};
+  LLVMStyle.IntegerLiteralSeparator = {
+      /*Binary=*/0,  /*BinaryMinDigits=*/0,
+      /*Decimal=*/0, /*DecimalMinDigits=*/0,
+      /*Hex=*/0,     /*HexMinDigits=*/0};
   LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
   LLVMStyle.JavaScriptWrapImports = true;
   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
diff --git a/clang/lib/Format/IntegerLiteralSeparatorFixer.cpp b/clang/lib/Format/IntegerLiteralSeparatorFixer.cpp
index 05e37c34a8a0..44034e44adec 100644
--- a/clang/lib/Format/IntegerLiteralSeparatorFixer.cpp
+++ b/clang/lib/Format/IntegerLiteralSeparatorFixer.cpp
@@ -69,6 +69,12 @@ IntegerLiteralSeparatorFixer::process(const Environment &Env,
   if (SkipBinary && SkipDecimal && SkipHex)
     return {};
 
+  const auto BinaryMinDigits =
+      std::max((int)Option.BinaryMinDigits, Binary + 1);
+  const auto DecimalMinDigits =
+      std::max((int)Option.DecimalMinDigits, Decimal + 1);
+  const auto HexMinDigits = std::max((int)Option.HexMinDigits, Hex + 1);
+
   const auto &SourceMgr = Env.getSourceManager();
   AffectedRangeManager AffectedRangeMgr(SourceMgr, Env.getCharRanges());
 
@@ -106,17 +112,18 @@ IntegerLiteralSeparatorFixer::process(const Environment &Env,
         (IsBase16 && SkipHex) || B == Base::Other) {
       continue;
     }
+    if (Style.isCpp()) {
+      if (const auto Pos = Text.find_first_of("_i"); Pos != StringRef::npos) {
+        Text = Text.substr(0, Pos);
+        Length = Pos;
+      }
+    }
     if ((IsBase10 && Text.find_last_of(".eEfFdDmM") != StringRef::npos) ||
         (IsBase16 && Text.find_last_of(".pP") != StringRef::npos)) {
       continue;
     }
-    if (((IsBase2 && Binary < 0) || (IsBase10 && Decimal < 0) ||
-         (IsBase16 && Hex < 0)) &&
-        Text.find(Separator) == StringRef::npos) {
-      continue;
-    }
     const auto Start = Text[0] == '0' ? 2 : 0;
-    auto End = Text.find_first_of("uUlLzZn");
+    auto End = Text.find_first_of("uUlLzZn", Start);
     if (End == StringRef::npos)
       End = Length;
     if (Start > 0 || End < Length) {
@@ -124,19 +131,30 @@ IntegerLiteralSeparatorFixer::process(const Environment &Env,
       Text = Text.substr(Start, Length);
     }
     auto DigitsPerGroup = Decimal;
-    if (IsBase2)
+    auto MinDigits = DecimalMinDigits;
+    if (IsBase2) {
       DigitsPerGroup = Binary;
-    else if (IsBase16)
+      MinDigits = BinaryMinDigits;
+    } else if (IsBase16) {
       DigitsPerGroup = Hex;
-    if (DigitsPerGroup > 0 && checkSeparator(Text, DigitsPerGroup))
+      MinDigits = HexMinDigits;
+    }
+    const auto SeparatorCount = Text.count(Separator);
+    const int DigitCount = Length - SeparatorCount;
+    const bool RemoveSeparator = DigitsPerGroup < 0 || DigitCount < MinDigits;
+    if (RemoveSeparator && SeparatorCount == 0)
+      continue;
+    if (!RemoveSeparator && SeparatorCount > 0 &&
+        checkSeparator(Text, DigitsPerGroup)) {
       continue;
+    }
+    const auto &Formatted =
+        format(Text, DigitsPerGroup, DigitCount, RemoveSeparator);
+    assert(Formatted != Text);
     if (Start > 0)
       Location = Location.getLocWithOffset(Start);
-    if (const auto &Formatted = format(Text, DigitsPerGroup);
-        Formatted != Text) {
-      cantFail(Result.add(
-          tooling::Replacement(SourceMgr, Location, Length, Formatted)));
-    }
+    cantFail(Result.add(
+        tooling::Replacement(SourceMgr, Location, Length, Formatted)));
   }
 
   return {Result, 0};
@@ -153,9 +171,9 @@ bool IntegerLiteralSeparatorFixer::checkSeparator(
         return false;
       I = 0;
     } else {
-      ++I;
       if (I == DigitsPerGroup)
         return false;
+      ++I;
     }
   }
 
@@ -163,23 +181,20 @@ bool IntegerLiteralSeparatorFixer::checkSeparator(
 }
 
 std::string IntegerLiteralSeparatorFixer::format(const StringRef IntegerLiteral,
-                                                 int DigitsPerGroup) const {
+                                                 int DigitsPerGroup,
+                                                 int DigitCount,
+                                                 bool RemoveSeparator) const {
   assert(DigitsPerGroup != 0);
 
   std::string Formatted;
 
-  if (DigitsPerGroup < 0) {
+  if (RemoveSeparator) {
     for (auto C : IntegerLiteral)
       if (C != Separator)
         Formatted.push_back(C);
     return Formatted;
   }
 
-  int DigitCount = 0;
-  for (auto C : IntegerLiteral)
-    if (C != Separator)
-      ++DigitCount;
-
   int Remainder = DigitCount % DigitsPerGroup;
 
   int I = 0;
diff --git a/clang/lib/Format/IntegerLiteralSeparatorFixer.h b/clang/lib/Format/IntegerLiteralSeparatorFixer.h
index 156bf5c14fca..2c158e4473bf 100644
--- a/clang/lib/Format/IntegerLiteralSeparatorFixer.h
+++ b/clang/lib/Format/IntegerLiteralSeparatorFixer.h
@@ -27,7 +27,8 @@ public:
 
 private:
   bool checkSeparator(const StringRef IntegerLiteral, int DigitsPerGroup) const;
-  std::string format(const StringRef IntegerLiteral, int DigitsPerGroup) const;
+  std::string format(const StringRef IntegerLiteral, int DigitsPerGroup,
+                     int DigitCount, bool RemoveSeparator) const;
 
   char Separator;
 };
diff --git a/clang/lib/Format/UnwrappedLineParser.cpp b/clang/lib/Format/UnwrappedLineParser.cpp
index 7e3957e62d3a..7a49b189b481 100644
--- a/clang/lib/Format/UnwrappedLineParser.cpp
+++ b/clang/lib/Format/UnwrappedLineParser.cpp
@@ -2739,16 +2739,17 @@ void UnwrappedLineParser::handleAttributes() {
   // Handle AttributeMacro, e.g. `if (x) UNLIKELY`.
   if (FormatTok->is(TT_AttributeMacro))
     nextToken();
-  handleCppAttributes();
+  if (FormatTok->is(tok::l_square))
+    handleCppAttributes();
 }
 
 bool UnwrappedLineParser::handleCppAttributes() {
   // Handle [[likely]] / [[unlikely]] attributes.
-  if (FormatTok->is(tok::l_square) && tryToParseSimpleAttribute()) {
-    parseSquare();
-    return true;
-  }
-  return false;
+  assert(FormatTok->is(tok::l_square));
+  if (!tryToParseSimpleAttribute())
+    return false;
+  parseSquare();
+  return true;
 }
 
 /// Returns whether \c Tok begins a block.
@@ -3849,13 +3850,13 @@ void UnwrappedLineParser::parseJavaEnumBody() {
 void UnwrappedLineParser::parseRecord(bool ParseAsExpr) {
   const FormatToken &InitialToken = *FormatTok;
   nextToken();
-  handleAttributes();
 
   // The actual identifier can be a nested name specifier, and in macros
   // it is often token-pasted.
+  // An [[attribute]] can be before the identifier.
   while (FormatTok->isOneOf(tok::identifier, tok::coloncolon, tok::hashhash,
                             tok::kw___attribute, tok::kw___declspec,
-                            tok::kw_alignas) ||
+                            tok::kw_alignas, tok::l_square) ||
          ((Style.Language == FormatStyle::LK_Java || Style.isJavaScript()) &&
           FormatTok->isOneOf(tok::period, tok::comma))) {
     if (Style.isJavaScript() &&
@@ -3869,16 +3870,15 @@ void UnwrappedLineParser::parseRecord(bool ParseAsExpr) {
         continue;
       }
     }
+    if (FormatTok->is(tok::l_square) && handleCppAttributes())
+      continue;
     bool IsNonMacroIdentifier =
         FormatTok->is(tok::identifier) &&
         FormatTok->TokenText != FormatTok->TokenText.upper();
     nextToken();
     // We can have macros in between 'class' and the class name.
-    if (!IsNonMacroIdentifier) {
-      if (FormatTok->is(tok::l_paren)) {
-        parseParens();
-      }
-    }
+    if (!IsNonMacroIdentifier && FormatTok->is(tok::l_paren))
+      parseParens();
   }
 
   // Note that parsing away template declarations here leads to incorrectly
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
index a7d2d55a06f8..a236be0a4daf 100644
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -11,15 +11,10 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
-#include <__algorithm/iter_swap.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
-#include <__assert>
-#include <__bit/blsr.h>
-#include <__bit/countl.h>
-#include <__bit/countr.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
@@ -28,10 +23,11 @@
 #include <__iterator/iterator_traits.h>
 #include <__memory/destruct_n.h>
 #include <__memory/unique_ptr.h>
-#include <__type_traits/conditional.h>
 #include <__type_traits/is_arithmetic.h>
+#include <__type_traits/is_trivially_copy_assignable.h>
+#include <__type_traits/is_trivially_copy_constructible.h>
 #include <__utility/move.h>
-#include <__utility/pair.h>
+#include <bit>
 #include <climits>
 #include <cstdint>
 
@@ -132,7 +128,8 @@ template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI
 unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
                  _Compare __c) {
-  using _Ops   = _IterOps<_AlgPolicy>;
+  using _Ops = _IterOps<_AlgPolicy>;
+
   unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
   if (__c(*__x4, *__x3)) {
     _Ops::iter_swap(__x3, __x4);
@@ -187,7 +184,7 @@ _LIBCPP_HIDE_FROM_ABI unsigned __sort5_wrap_policy(
     _Compare __c) {
   using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
   _WrappedComp __wrapped_comp(__c);
-  return std::__sort5<_WrappedComp, _ForwardIterator>(
+  return std::__sort5<_WrappedComp>(
       std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp);
 }
 
@@ -212,13 +209,6 @@ using __use_branchless_sort =
     integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
                                 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
 
-namespace __detail {
-
-// Size in bits for the bitset in use.
-enum { __block_size = sizeof(uint64_t) * 8 };
-
-} // namespace __detail
-
 // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
@@ -278,15 +268,10 @@ __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2,
   std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
 }
 
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
-__sort5_maybe_branchless(
-    _RandomAccessIterator __x1,
-    _RandomAccessIterator __x2,
-    _RandomAccessIterator __x3,
-    _RandomAccessIterator __x4,
-    _RandomAccessIterator __x5,
-    _Compare __c) {
+__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
   std::__cond_swap<_Compare>(__x1, __x2, __c);
   std::__cond_swap<_Compare>(__x4, __x5, __c);
   std::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c);
@@ -315,48 +300,34 @@ _LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_sort(_BidirectionalIterator __fir
   }
 }
 
-// Sort the iterator range [__first, __last) using the comparator __comp using
-// the insertion sort algorithm.
 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 _LIBCPP_HIDE_FROM_ABI
 void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
 
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-  if (__first == __last)
-    return;
-  _BidirectionalIterator __i = __first;
-  for (++__i; __i != __last; ++__i) {
-    _BidirectionalIterator __j = __i;
-    --__j;
-    if (__comp(*__i, *__j)) {
-      value_type __t(_Ops::__iter_move(__i));
-      _BidirectionalIterator __k = __j;
-      __j                        = __i;
-      do {
+  if (__first != __last) {
+    _BidirectionalIterator __i = __first;
+    for (++__i; __i != __last; ++__i) {
+      _BidirectionalIterator __j = __i;
+      value_type __t(_Ops::__iter_move(__j));
+      for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
         *__j = _Ops::__iter_move(__k);
-        __j  = __k;
-      } while (__j != __first && __comp(__t, *--__k));
       *__j = std::move(__t);
     }
   }
 }
 
-// Sort the iterator range [__first, __last) using the comparator __comp using
-// the insertion sort algorithm.  Insertion sort has two loops, outer and inner.
-// The implementation below has not bounds check (unguarded) for the inner loop.
-// Assumes that there is an element in the position (__first - 1) and that each
-// element in the input range is greater or equal to the element at __first - 1.
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
-_LIBCPP_HIDE_FROM_ABI void
-__insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+_LIBCPP_HIDE_FROM_ABI
+void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-  if (__first == __last)
-    return;
-  for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
-    _RandomAccessIterator __j = __i - difference_type(1);
+  _RandomAccessIterator __j = __first + difference_type(2);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
+  for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
       value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
@@ -364,9 +335,10 @@ __insertion_sort_unguarded(_RandomAccessIterator __first, _RandomAccessIterator
       do {
         *__j = _Ops::__iter_move(__k);
         __j = __k;
-      } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
+      } while (__j != __first && __comp(__t, *--__k));
       *__j = std::move(__t);
     }
+    __j = __i;
   }
 }
 
@@ -387,7 +359,7 @@ _LIBCPP_HIDDEN bool __insertion_sort_incomplete(
     return true;
   case 2:
     if (__comp(*--__last, *__first))
-      _Ops::iter_swap(__first, __last);
+      _IterOps<_AlgPolicy>::iter_swap(__first, __last);
     return true;
   case 3:
     std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
@@ -456,336 +428,17 @@ void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterat
   }
 }
 
-template <class _AlgPolicy, class _RandomAccessIterator>
-inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(
-    _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) {
-  using _Ops = _IterOps<_AlgPolicy>;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  // Swap one pair on each iteration as long as both bitsets have at least one
-  // element for swapping.
-  while (__left_bitset != 0 && __right_bitset != 0) {
-    difference_type tz_left  = __libcpp_ctz(__left_bitset);
-    __left_bitset            = __libcpp_blsr(__left_bitset);
-    difference_type tz_right = __libcpp_ctz(__right_bitset);
-    __right_bitset           = __libcpp_blsr(__right_bitset);
-    _Ops::iter_swap(__first + tz_left, __last - tz_right);
-  }
-}
-
-template <class _Compare,
-          class _RandomAccessIterator,
-          class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
-inline _LIBCPP_HIDE_FROM_ABI void
-__populate_left_bitset(_RandomAccessIterator __first, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset) {
-  // Possible vectorization. With a proper "-march" flag, the following loop
-  // will be compiled into a set of SIMD instructions.
-  _RandomAccessIterator __iter = __first;
-  for (int __j = 0; __j < __detail::__block_size;) {
-    bool __comp_result = !__comp(*__iter, __pivot);
-    __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
-    __j++;
-    ++__iter;
-  }
-}
-
-template <class _Compare,
-          class _RandomAccessIterator,
-          class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
-inline _LIBCPP_HIDE_FROM_ABI void
-__populate_right_bitset(_RandomAccessIterator __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __right_bitset) {
-  // Possible vectorization. With a proper "-march" flag, the following loop
-  // will be compiled into a set of SIMD instructions.
-  _RandomAccessIterator __iter = __lm1;
-  for (int __j = 0; __j < __detail::__block_size;) {
-    bool __comp_result = __comp(*__iter, __pivot);
-    __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
-    __j++;
-    --__iter;
-  }
-}
-
-template <class _AlgPolicy,
-          class _Compare,
-          class _RandomAccessIterator,
-          class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
-inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks(
-    _RandomAccessIterator& __first,
-    _RandomAccessIterator& __lm1,
-    _Compare __comp,
-    _ValueType& __pivot,
-    uint64_t& __left_bitset,
-    uint64_t& __right_bitset) {
-  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  difference_type __remaining_len = __lm1 - __first + 1;
-  difference_type __l_size;
-  difference_type __r_size;
-  if (__left_bitset == 0 && __right_bitset == 0) {
-    __l_size = __remaining_len / 2;
-    __r_size = __remaining_len - __l_size;
-  } else if (__left_bitset == 0) {
-    // We know at least one side is a full block.
-    __l_size = __remaining_len - __detail::__block_size;
-    __r_size = __detail::__block_size;
-  } else { // if (__right_bitset == 0)
-    __l_size = __detail::__block_size;
-    __r_size = __remaining_len - __detail::__block_size;
-  }
-  // Record the comparison outcomes for the elements currently on the left side.
-  if (__left_bitset == 0) {
-    _RandomAccessIterator __iter = __first;
-    for (int j = 0; j < __l_size; j++) {
-      bool __comp_result = !__comp(*__iter, __pivot);
-      __left_bitset |= (static_cast<uint64_t>(__comp_result) << j);
-      ++__iter;
-    }
-  }
-  // Record the comparison outcomes for the elements currently on the right
-  // side.
-  if (__right_bitset == 0) {
-    _RandomAccessIterator __iter = __lm1;
-    for (int j = 0; j < __r_size; j++) {
-      bool __comp_result = __comp(*__iter, __pivot);
-      __right_bitset |= (static_cast<uint64_t>(__comp_result) << j);
-      --__iter;
-    }
-  }
-  std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
-  __first += (__left_bitset == 0) ? __l_size : 0;
-  __lm1 -= (__right_bitset == 0) ? __r_size : 0;
-}
-
-template <class _AlgPolicy, class _RandomAccessIterator>
-inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within(
-    _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, uint64_t& __left_bitset, uint64_t& __right_bitset) {
-  using _Ops = _IterOps<_AlgPolicy>;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  if (__left_bitset) {
-    // Swap within the left side.  Need to find set positions in the reverse
-    // order.
-    while (__left_bitset != 0) {
-      difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset);
-      __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1;
-      _RandomAccessIterator it = __first + __tz_left;
-      if (it != __lm1) {
-        _Ops::iter_swap(it, __lm1);
-      }
-      --__lm1;
-    }
-    __first = __lm1 + difference_type(1);
-  } else if (__right_bitset) {
-    // Swap within the right side.  Need to find set positions in the reverse
-    // order.
-    while (__right_bitset != 0) {
-      difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset);
-      __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1;
-      _RandomAccessIterator it = __lm1 - __tz_right;
-      if (it != __first) {
-        _Ops::iter_swap(it, __first);
-      }
-      ++__first;
-    }
-  }
-}
-
-// Partition [__first, __last) using the comparator __comp.  *__first has the
-// chosen pivot.  Elements that are equivalent are kept to the left of the
-// pivot.  Returns the iterator for the pivot and a bool value which is true if
-// the provided range is already sorted, false otherwise.  We assume that the
-// length of the range is at least three elements.
-//
-// __bitset_partition uses bitsets for storing outcomes of the comparisons
-// between the pivot and other elements.
-template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
-_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
-__bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  using _Ops = _IterOps<_AlgPolicy>;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  _LIBCPP_ASSERT(__last - __first >= difference_type(3), "");
-
-  _RandomAccessIterator __begin = __first;
-  value_type __pivot(_Ops::__iter_move(__first));
-  // Find the first element greater than the pivot.
-  if (__comp(__pivot, *(__last - difference_type(1)))) {
-    // Not guarded since we know the last element is greater than the pivot.
-    while (!__comp(__pivot, *++__first)) {
-    }
-  } else {
-    while (++__first < __last && !__comp(__pivot, *__first)) {
-    }
-  }
-  // Find the last element less than or equal to the pivot.
-  if (__first < __last) {
-    // It will be always guarded because __introsort will do the median-of-three
-    // before calling this.
-    while (__comp(__pivot, *--__last)) {
-    }
-  }
-  // If the first element greater than the pivot is at or after the
-  // last element less than or equal to the pivot, then we have covered the
-  // entire range without swapping elements.  This implies the range is already
-  // partitioned.
-  bool __already_partitioned = __first >= __last;
-  if (!__already_partitioned) {
-    _Ops::iter_swap(__first, __last);
-    ++__first;
-  }
-
-  // In [__first, __last) __last is not inclusive. From now on, it uses last
-  // minus one to be inclusive on both sides.
-  _RandomAccessIterator __lm1 = __last - difference_type(1);
-  uint64_t __left_bitset      = 0;
-  uint64_t __right_bitset     = 0;
-
-  // Reminder: length = __lm1 - __first + 1.
-  while (__lm1 - __first >= 2 * __detail::__block_size - 1) {
-    // Record the comparison outcomes for the elements currently on the left
-    // side.
-    if (__left_bitset == 0)
-      std::__populate_left_bitset<_Compare>(__first, __comp, __pivot, __left_bitset);
-    // Record the comparison outcomes for the elements currently on the right
-    // side.
-    if (__right_bitset == 0)
-      std::__populate_right_bitset<_Compare>(__lm1, __comp, __pivot, __right_bitset);
-    // Swap the elements recorded to be the candidates for swapping in the
-    // bitsets.
-    std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
-    // Only advance the iterator if all the elements that need to be moved to
-    // other side were moved.
-    __first += (__left_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
-    __lm1 -= (__right_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
-  }
-  // Now, we have a less-than a block worth of elements on at least one of the
-  // sides.
-  std::__bitset_partition_partial_blocks<_AlgPolicy, _Compare>(
-      __first, __lm1, __comp, __pivot, __left_bitset, __right_bitset);
-  // At least one the bitsets would be empty.  For the non-empty one, we need to
-  // properly partition the elements that appear within that bitset.
-  std::__swap_bitmap_pos_within<_AlgPolicy>(__first, __lm1, __left_bitset, __right_bitset);
-
-  // Move the pivot to its correct position.
-  _RandomAccessIterator __pivot_pos = __first - difference_type(1);
-  if (__begin != __pivot_pos) {
-    *__begin = _Ops::__iter_move(__pivot_pos);
-  }
-  *__pivot_pos = std::move(__pivot);
-  return std::make_pair(__pivot_pos, __already_partitioned);
-}
-
-// Partition [__first, __last) using the comparator __comp.  *__first has the
-// chosen pivot.  Elements that are equivalent are kept to the right of the
-// pivot.  Returns the iterator for the pivot and a bool value which is true if
-// the provided range is already sorted, false otherwise.  We assume that the
-// length of the range is at least three elements.
-template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
-_LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
-__partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  using _Ops = _IterOps<_AlgPolicy>;
-  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  _LIBCPP_ASSERT(__last - __first >= difference_type(3), "");
-  _RandomAccessIterator __begin = __first;
-  value_type __pivot(_Ops::__iter_move(__first));
-  // Find the first element greater or equal to the pivot.  It will be always
-  // guarded because __introsort will do the median-of-three before calling
-  // this.
-  while (__comp(*++__first, __pivot))
-    ;
-
-  // Find the last element less than the pivot.
-  if (__begin == __first - difference_type(1)) {
-    while (__first < __last && !__comp(*--__last, __pivot))
-      ;
-  } else {
-    // Guarded.
-    while (!__comp(*--__last, __pivot))
-      ;
-  }
-
-  // If the first element greater than or equal to the pivot is at or after the
-  // last element less than the pivot, then we have covered the entire range
-  // without swapping elements.  This implies the range is already partitioned.
-  bool __already_partitioned = __first >= __last;
-  // Go through the remaining elements.  Swap pairs of elements (one to the
-  // right of the pivot and the other to left of the pivot) that are not on the
-  // correct side of the pivot.
-  while (__first < __last) {
-    _Ops::iter_swap(__first, __last);
-    while (__comp(*++__first, __pivot))
-      ;
-    while (!__comp(*--__last, __pivot))
-      ;
-  }
-  // Move the pivot to its correct position.
-  _RandomAccessIterator __pivot_pos = __first - difference_type(1);
-  if (__begin != __pivot_pos) {
-    *__begin = _Ops::__iter_move(__pivot_pos);
-  }
-  *__pivot_pos = std::move(__pivot);
-  return std::make_pair(__pivot_pos, __already_partitioned);
-}
-
-// Similar to the above function.  Elements equivalent to the pivot are put to
-// the left of the pivot.  Returns the iterator to the pivot element.
-template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
-_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
-__partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+                 typename iterator_traits<_RandomAccessIterator>::difference_type __depth) {
   using _Ops = _IterOps<_AlgPolicy>;
-  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
-  _RandomAccessIterator __begin = __first;
-  value_type __pivot(_Ops::__iter_move(__first));
-  if (__comp(__pivot, *(__last - difference_type(1)))) {
-    // Guarded.
-    while (!__comp(__pivot, *++__first)) {
-    }
-  } else {
-    while (++__first < __last && !__comp(__pivot, *__first)) {
-    }
-  }
-
-  if (__first < __last) {
-    // It will be always guarded because __introsort will do the
-    // median-of-three before calling this.
-    while (__comp(__pivot, *--__last)) {
-    }
-  }
-  while (__first < __last) {
-    _Ops::iter_swap(__first, __last);
-    while (!__comp(__pivot, *++__first))
-      ;
-    while (__comp(__pivot, *--__last))
-      ;
-  }
-  _RandomAccessIterator __pivot_pos = __first - difference_type(1);
-  if (__begin != __pivot_pos) {
-    *__begin = _Ops::__iter_move(__pivot_pos);
-  }
-  *__pivot_pos = std::move(__pivot);
-  return __first;
-}
 
-// The main sorting function.  Implements introsort combined with other ideas:
-//  - option of using block quick sort for partitioning,
-//  - guarded and unguarded insertion sort for small lengths,
-//  - Tuckey's ninther technique for computing the pivot,
-//  - check on whether partition was not required.
-// The implementation is partly based on Orson Peters' pattern-defeating
-// quicksort, published at: <https://github.com/orlp/pdqsort>.
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition>
-void __introsort(_RandomAccessIterator __first,
-                 _RandomAccessIterator __last,
-                 _Compare __comp,
-                 typename iterator_traits<_RandomAccessIterator>::difference_type __depth,
-                 bool __leftmost = true) {
-  using _Ops = _IterOps<_AlgPolicy>;
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-  using _Comp_ref = __comp_ref_type<_Compare>;
-  // Upper bound for using insertion sort for sorting.
-  _LIBCPP_CONSTEXPR difference_type __limit = 24;
-  // Lower bound for using Tuckey's ninther technique for median computation.
-  _LIBCPP_CONSTEXPR difference_type __ninther_threshold = 128;
+  typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+  const difference_type __limit =
+      is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6;
   while (true) {
+  __restart:
     difference_type __len = __last - __first;
     switch (__len) {
     case 0:
@@ -793,7 +446,7 @@ void __introsort(_RandomAccessIterator __first,
       return;
     case 2:
       if (__comp(*--__last, *__first))
-        _Ops::iter_swap(__first, __last);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
       return;
     case 3:
       std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
@@ -808,60 +461,127 @@ void __introsort(_RandomAccessIterator __first,
           --__last, __comp);
       return;
     }
-    // Use insertion sort if the length of the range is below the specified limit.
-    if (__len < __limit) {
-      if (__leftmost) {
-        std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
-      } else {
-        std::__insertion_sort_unguarded<_AlgPolicy, _Compare>(__first, __last, __comp);
-      }
+    if (__len <= __limit) {
+      std::__insertion_sort_3<_AlgPolicy, _Compare>(__first, __last, __comp);
       return;
     }
+    // __len > 5
     if (__depth == 0) {
       // Fallback to heap sort as Introsort suggests.
       std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp);
       return;
     }
     --__depth;
+    _RandomAccessIterator __m = __first;
+    _RandomAccessIterator __lm1 = __last;
+    --__lm1;
+    unsigned __n_swaps;
     {
-      difference_type __half_len = __len / 2;
-      // Use Tuckey's ninther technique or median of 3 for pivot selection
-      // depending on the length of the range being sorted.
-      if (__len > __ninther_threshold) {
-        std::__sort3<_AlgPolicy, _Compare>(__first, __first + __half_len, __last - difference_type(1), __comp);
-        std::__sort3<_AlgPolicy, _Compare>(
-            __first + difference_type(1), __first + (__half_len - 1), __last - difference_type(2), __comp);
-        std::__sort3<_AlgPolicy, _Compare>(
-            __first + difference_type(2), __first + (__half_len + 1), __last - difference_type(3), __comp);
-        std::__sort3<_AlgPolicy, _Compare>(
-            __first + (__half_len - 1), __first + __half_len, __first + (__half_len + 1), __comp);
-        _Ops::iter_swap(__first, __first + __half_len);
+      difference_type __delta;
+      if (__len >= 1000) {
+        __delta = __len / 2;
+        __m += __delta;
+        __delta /= 2;
+        __n_swaps = std::__sort5_wrap_policy<_AlgPolicy, _Compare>(
+            __first, __first + __delta, __m, __m + __delta, __lm1, __comp);
       } else {
-        std::__sort3<_AlgPolicy, _Compare>(__first + __half_len, __first, __last - difference_type(1), __comp);
+        __delta = __len / 2;
+        __m += __delta;
+        __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, __lm1, __comp);
       }
     }
-    // The elements to the left of the current iterator range are already
-    // sorted.  If the current iterator range to be sorted is not the
-    // leftmost part of the entire iterator range and the pivot is same as
-    // the highest element in the range to the left, then we know that all
-    // the elements in the range [first, pivot] would be equal to the pivot,
-    // assuming the equal elements are put on the left side when
-    // partitioned.  This also means that we do not need to sort the left
-    // side of the partition.
-    if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
-      __first = std::__partition_with_equals_on_left<_AlgPolicy, _RandomAccessIterator, _Comp_ref>(
-          __first, __last, _Comp_ref(__comp));
-      continue;
+    // *__m is median
+    // partition [__first, __m) < *__m and *__m <= [__m, __last)
+    // (this inhibits tossing elements equivalent to __m around unnecessarily)
+    _RandomAccessIterator __i = __first;
+    _RandomAccessIterator __j = __lm1;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // The search going up is known to be guarded but the search coming down isn't.
+    // Prime the downward search with a guard.
+    if (!__comp(*__i, *__m)) // if *__first == *__m
+    {
+      // *__first == *__m, *__first doesn't go in first part
+      // manually guard downward moving __j against __i
+      while (true) {
+        if (__i == --__j) {
+          // *__first == *__m, *__m <= all other elements
+          // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
+          ++__i; // __first + 1
+          __j = __last;
+          if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
+          {
+            while (true) {
+              if (__i == __j)
+                return; // [__first, __last) all equivalent elements
+              if (__comp(*__first, *__i)) {
+                _Ops::iter_swap(__i, __j);
+                ++__n_swaps;
+                ++__i;
+                break;
+              }
+              ++__i;
+            }
+          }
+          // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
+          if (__i == __j)
+            return;
+          while (true) {
+            while (!__comp(*__first, *__i))
+              ++__i;
+            while (__comp(*__first, *--__j))
+              ;
+            if (__i >= __j)
+              break;
+            _Ops::iter_swap(__i, __j);
+            ++__n_swaps;
+            ++__i;
+          }
+          // [__first, __i) == *__first and *__first < [__i, __last)
+          // The first part is sorted, sort the second part
+          // std::__sort<_Compare>(__i, __last, __comp);
+          __first = __i;
+          goto __restart;
+        }
+        if (__comp(*__j, *__m)) {
+          _Ops::iter_swap(__i, __j);
+          ++__n_swaps;
+          break; // found guard for downward moving __j, now use unguarded partition
+        }
+      }
+    }
+    // It is known that *__i < *__m
+    ++__i;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // if not yet partitioned...
+    if (__i < __j) {
+      // known that *(__i - 1) < *__m
+      // known that __i <= __m
+      while (true) {
+        // __m still guards upward moving __i
+        while (__comp(*__i, *__m))
+          ++__i;
+        // It is now known that a guard exists for downward moving __j
+        while (!__comp(*--__j, *__m))
+          ;
+        if (__i > __j)
+          break;
+        _Ops::iter_swap(__i, __j);
+        ++__n_swaps;
+        // It is known that __m != __j
+        // If __m just moved, follow it
+        if (__m == __i)
+          __m = __j;
+        ++__i;
+      }
+    }
+    // [__first, __i) < *__m and *__m <= [__i, __last)
+    if (__i != __m && __comp(*__m, *__i)) {
+      _Ops::iter_swap(__i, __m);
+      ++__n_swaps;
     }
-    // Use bitset partition only if asked for.
-    auto __ret =
-        _UseBitSetPartition
-            ? std::__bitset_partition<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp)
-            : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp);
-    _RandomAccessIterator __i = __ret.first;
     // [__first, __i) < *__i and *__i <= [__i+1, __last)
     // If we were given a perfect partition, see if insertion sort is quick...
-    if (__ret.second) {
+    if (__n_swaps == 0) {
       using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
       _WrappedComp __wrapped_comp(__comp);
       bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp);
@@ -877,11 +597,14 @@ void __introsort(_RandomAccessIterator __first,
         }
       }
     }
-    // Sort the left partiton recursively and the right partition with tail recursion elimination.
-    std::__introsort<_AlgPolicy, _Compare, _RandomAccessIterator, _UseBitSetPartition>(
-        __first, __i, __comp, __depth, __leftmost);
-    __leftmost = false;
-    __first    = ++__i;
+    // sort smaller range with recursive call and larger with tail recursion elimination
+    if (__i - __first < __last - __i) {
+      std::__introsort<_AlgPolicy, _Compare>(__first, __i, __comp, __depth);
+      __first = ++__i;
+    } else {
+      std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth);
+      __last = __i;
+    }
   }
 }
 
@@ -913,14 +636,7 @@ _LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator
   using _AlgPolicy = typename _Unwrap::_AlgPolicy;
   using _Compare = typename _Unwrap::_Comp;
   _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
-  // Only use bitset partitioning for arithmetic types.  We should also check
-  // that the default comparator is in use so that we are sure that there are no
-  // branches in the comparator.
-  std::__introsort<_AlgPolicy,
-                   _Compare,
-                   _RandomAccessIterator,
-                   __use_branchless_sort<_Compare, _RandomAccessIterator>::value>(
-      __first, __last, __comp, __depth_limit);
+  std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit);
 }
 
 template <class _Compare, class _Tp>
diff --git a/libcxx/include/__config b/libcxx/include/__config
index 2f11f3b7d495..581ada45b3f0 100644
--- a/libcxx/include/__config
+++ b/libcxx/include/__config
@@ -23,6 +23,7 @@
 #endif
 
 #if defined(__apple_build_version__)
+// Given AppleClang XX.Y.Z, _LIBCPP_APPLE_CLANG_VER is XXYZ (e.g. AppleClang 14.0.3 => 1403)
 #  define _LIBCPP_COMPILER_CLANG_BASED
 #  define _LIBCPP_APPLE_CLANG_VER (__apple_build_version__ / 10000)
 #elif defined(__clang__)
diff --git a/libcxx/include/source_location b/libcxx/include/source_location
index 4c4a09618ada..e9e852a6e461 100644
--- a/libcxx/include/source_location
+++ b/libcxx/include/source_location
@@ -35,7 +35,8 @@ namespace std {
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_source_location)
+#if _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_source_location) &&                                               \
+    !(defined(_LIBCPP_APPLE_CLANG_VER) && _LIBCPP_APPLE_CLANG_VER <= 1403)
 
 class source_location {
   // The names source_location::__impl, _M_file_name, _M_function_name, _M_line, and _M_column
@@ -78,7 +79,8 @@ public:
   }
 };
 
-#endif // _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_source_location)
+#endif // _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_source_location) && !(defined(_LIBCPP_APPLE_CLANG_VER) &&
+       // _LIBCPP_APPLE_CLANG_VER <= 1403)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/libcxx/include/version b/libcxx/include/version
index 28c4a50cdab7..258dd641e144 100644
--- a/libcxx/include/version
+++ b/libcxx/include/version
@@ -366,7 +366,7 @@ __cpp_lib_void_t                                        201411L <type_traits>
 # define __cpp_lib_shared_ptr_arrays                    201707L
 # define __cpp_lib_shift                                201806L
 // # define __cpp_lib_smart_ptr_for_overwrite              202002L
-# if __has_builtin(__builtin_source_location)
+# if __has_builtin(__builtin_source_location) && !(defined(_LIBCPP_APPLE_CLANG_VER) && _LIBCPP_APPLE_CLANG_VER <= 1403)
 #   define __cpp_lib_source_location                    201907L
 # endif
 # define __cpp_lib_span                                 202002L
diff --git a/llvm/include/llvm/ADT/AddressRanges.h b/llvm/include/llvm/ADT/AddressRanges.h
index 415d30bbb5cf..f2052d82e7c1 100644
--- a/llvm/include/llvm/ADT/AddressRanges.h
+++ b/llvm/include/llvm/ADT/AddressRanges.h
@@ -28,11 +28,7 @@ public:
   uint64_t start() const { return Start; }
   uint64_t end() const { return End; }
   uint64_t size() const { return End - Start; }
-  uint64_t empty() const { return size() == 0; }
   bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
-  bool contains(const AddressRange &R) const {
-    return Start <= R.Start && R.End <= End;
-  }
   bool intersects(const AddressRange &R) const {
     return Start < R.End && R.Start < End;
   }
@@ -49,163 +45,101 @@ private:
   uint64_t End = 0;
 };
 
-/// The AddressRangesBase class presents the base functionality for the
-/// normalized address ranges collection. This class keeps a sorted vector
-/// of AddressRange-like objects and can perform searches efficiently.
-/// The address ranges are always sorted and never contain any invalid,
-/// empty or intersected address ranges.
-
-template <typename T> class AddressRangesBase {
+/// The AddressRanges class helps normalize address range collections.
+/// This class keeps a sorted vector of AddressRange objects and can perform
+/// insertions and searches efficiently. The address ranges are always sorted
+/// and never contain any invalid or empty address ranges.
+/// Intersecting([100,200), [150,300)) and adjacent([100,200), [200,300))
+/// address ranges are combined during insertion.
+class AddressRanges {
 protected:
-  using Collection = SmallVector<T>;
+  using Collection = SmallVector<AddressRange>;
   Collection Ranges;
 
 public:
   void clear() { Ranges.clear(); }
   bool empty() const { return Ranges.empty(); }
-  bool contains(uint64_t Addr) const {
-    return find(Addr, Addr + 1) != Ranges.end();
-  }
+  bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
   bool contains(AddressRange Range) const {
-    return find(Range.start(), Range.end()) != Ranges.end();
+    return find(Range) != Ranges.end();
   }
-  void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
-  size_t size() const { return Ranges.size(); }
-
-  std::optional<T> getRangeThatContains(uint64_t Addr) const {
-    typename Collection::const_iterator It = find(Addr, Addr + 1);
+  std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
     if (It == Ranges.end())
       return std::nullopt;
 
     return *It;
   }
-
-  typename Collection::const_iterator begin() const { return Ranges.begin(); }
-  typename Collection::const_iterator end() const { return Ranges.end(); }
-
-  const T &operator[](size_t i) const {
+  Collection::const_iterator insert(AddressRange Range);
+  void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
+  size_t size() const { return Ranges.size(); }
+  bool operator==(const AddressRanges &RHS) const {
+    return Ranges == RHS.Ranges;
+  }
+  const AddressRange &operator[](size_t i) const {
     assert(i < Ranges.size());
     return Ranges[i];
   }
-
-  bool operator==(const AddressRangesBase<T> &RHS) const {
-    return Ranges == RHS.Ranges;
-  }
+  Collection::const_iterator begin() const { return Ranges.begin(); }
+  Collection::const_iterator end() const { return Ranges.end(); }
 
 protected:
-  typename Collection::const_iterator find(uint64_t Start, uint64_t End) const {
-    if (Start >= End)
-      return Ranges.end();
-
-    auto It =
-        std::partition_point(Ranges.begin(), Ranges.end(), [=](const T &R) {
-          return AddressRange(R).start() <= Start;
-        });
-
-    if (It == Ranges.begin())
-      return Ranges.end();
-
-    --It;
-    if (End > AddressRange(*It).end())
-      return Ranges.end();
-
-    return It;
-  }
+  Collection::const_iterator find(uint64_t Addr) const;
+  Collection::const_iterator find(AddressRange Range) const;
 };
 
-/// The AddressRanges class helps normalize address range collections.
-/// This class keeps a sorted vector of AddressRange objects and can perform
-/// insertions and searches efficiently. Intersecting([100,200), [150,300))
-/// and adjacent([100,200), [200,300)) address ranges are combined during
-/// insertion.
-class AddressRanges : public AddressRangesBase<AddressRange> {
-public:
-  Collection::const_iterator insert(AddressRange Range) {
-    if (Range.empty())
-      return Ranges.end();
-
-    auto It = llvm::upper_bound(Ranges, Range);
-    auto It2 = It;
-    while (It2 != Ranges.end() && It2->start() <= Range.end())
-      ++It2;
-    if (It != It2) {
-      Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
-      It = Ranges.erase(It, It2);
-    }
-    if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
-      --It;
-      *It = {It->start(), std::max(It->end(), Range.end())};
-      return It;
-    }
-
-    return Ranges.insert(It, Range);
-  }
-};
-
-class AddressRangeValuePair {
-public:
-  operator AddressRange() const { return Range; }
-
-  AddressRange Range;
-  int64_t Value = 0;
-};
-
-inline bool operator==(const AddressRangeValuePair &LHS,
-                       const AddressRangeValuePair &RHS) {
-  return LHS.Range == RHS.Range && LHS.Value == RHS.Value;
-}
-
 /// AddressRangesMap class maps values to the address ranges.
-/// It keeps normalized address ranges and corresponding values.
-/// This class keeps a sorted vector of AddressRangeValuePair objects
-/// and can perform insertions and searches efficiently.
-/// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting
-/// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address
-/// ranges are not combined during insertion.
-class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> {
+/// It keeps address ranges and corresponding values. If ranges
+/// are combined during insertion, then combined range keeps
+/// newly inserted value.
+template <typename T> class AddressRangesMap : protected AddressRanges {
 public:
-  void insert(AddressRange Range, int64_t Value) {
-    if (Range.empty())
+  void clear() {
+    Ranges.clear();
+    Values.clear();
+  }
+  bool empty() const { return AddressRanges::empty(); }
+  bool contains(uint64_t Addr) const { return AddressRanges::contains(Addr); }
+  bool contains(AddressRange Range) const {
+    return AddressRanges::contains(Range);
+  }
+  void insert(AddressRange Range, T Value) {
+    size_t InputSize = Ranges.size();
+    Collection::const_iterator RangesIt = AddressRanges::insert(Range);
+    if (RangesIt == Ranges.end())
       return;
 
-    // Search for range which is less than or equal incoming Range.
-    auto It = std::partition_point(Ranges.begin(), Ranges.end(),
-                                   [=](const AddressRangeValuePair &R) {
-                                     return R.Range.start() <= Range.start();
-                                   });
-
-    if (It != Ranges.begin())
-      It--;
-
-    while (!Range.empty()) {
-      // Inserted range does not overlap with any range.
-      // Store it into the Ranges collection.
-      if (It == Ranges.end() || Range.end() <= It->Range.start()) {
-        Ranges.insert(It, {Range, Value});
-        return;
-      }
-
-      // Inserted range partially overlaps with current range.
-      // Store not overlapped part of inserted range.
-      if (Range.start() < It->Range.start()) {
-        It = Ranges.insert(It, {{Range.start(), It->Range.start()}, Value});
-        It++;
-        Range = {It->Range.start(), Range.end()};
-        continue;
-      }
-
-      // Inserted range fully overlaps with current range.
-      if (Range.end() <= It->Range.end())
-        return;
-
-      // Inserted range partially overlaps with current range.
-      // Remove overlapped part from the inserted range.
-      if (Range.start() < It->Range.end())
-        Range = {It->Range.end(), Range.end()};
-
-      It++;
-    }
+    // make Values match to Ranges.
+    size_t Idx = RangesIt - Ranges.begin();
+    typename ValuesCollection::iterator ValuesIt = Values.begin() + Idx;
+    if (InputSize < Ranges.size())
+      Values.insert(ValuesIt, T());
+    else if (InputSize > Ranges.size())
+      Values.erase(ValuesIt, ValuesIt + InputSize - Ranges.size());
+    assert(Ranges.size() == Values.size());
+
+    // set value to the inserted or combined range.
+    Values[Idx] = Value;
   }
+  size_t size() const {
+    assert(Ranges.size() == Values.size());
+    return AddressRanges::size();
+  }
+  std::optional<std::pair<AddressRange, T>>
+  getRangeValueThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
+    if (It == Ranges.end())
+      return std::nullopt;
+
+    return std::make_pair(*It, Values[It - Ranges.begin()]);
+  }
+  std::pair<AddressRange, T> operator[](size_t Idx) const {
+    return std::make_pair(Ranges[Idx], Values[Idx]);
+  }
+
+protected:
+  using ValuesCollection = SmallVector<T>;
+  ValuesCollection Values;
 };
 
 } // namespace llvm
diff --git a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
index 9c7f24e69d48..5b0ea339c4d6 100644
--- a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
+++ b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
@@ -21,7 +21,7 @@ class DeclContext;
 
 /// Mapped value in the address map is the offset to apply to the
 /// linked address.
-using RangesTy = AddressRangesMap;
+using RangesTy = AddressRangesMap<int64_t>;
 
 // FIXME: Delete this structure.
 struct PatchLocation {
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index eed3d820c120..d9cde609e599 100644
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -21361,10 +21361,9 @@ static SDValue reduceBuildVecToShuffleWithZero(SDNode *BV, SelectionDAG &DAG) {
       // the source vector. The high bits map to zero. We will use a zero vector
       // as the 2nd source operand of the shuffle, so use the 1st element of
       // that vector (mask value is number-of-elements) for the high bits.
-      if (i % ZextRatio == 0)
-        ShufMask[i] = Extract.getConstantOperandVal(1);
-      else
-        ShufMask[i] = NumMaskElts;
+      int Low = DAG.getDataLayout().isBigEndian() ? (ZextRatio - 1) : 0;
+      ShufMask[i] = (i % ZextRatio == Low) ? Extract.getConstantOperandVal(1)
+                                           : NumMaskElts;
     }
 
     // Undef elements of the build vector remain undef because we initialize
diff --git a/llvm/lib/DWARFLinker/DWARFLinker.cpp b/llvm/lib/DWARFLinker/DWARFLinker.cpp
index d302d61894fa..9f6e54377ede 100644
--- a/llvm/lib/DWARFLinker/DWARFLinker.cpp
+++ b/llvm/lib/DWARFLinker/DWARFLinker.cpp
@@ -1659,7 +1659,7 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
   DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
                                     OrigDwarf.getDWARFObj().getRangesSection(),
                                     OrigDwarf.isLittleEndian(), AddressSize);
-  std::optional<AddressRangeValuePair> CachedRange;
+  std::optional<std::pair<AddressRange, int64_t>> CachedRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
   uint64_t UnitBaseAddress =
@@ -1687,9 +1687,9 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
         }
 
         if (!CachedRange ||
-            !CachedRange->Range.contains(Range.StartAddress + BaseAddress))
-          CachedRange = FunctionRanges.getRangeThatContains(Range.StartAddress +
-                                                            BaseAddress);
+            !CachedRange->first.contains(Range.StartAddress + BaseAddress))
+          CachedRange = FunctionRanges.getRangeValueThatContains(
+              Range.StartAddress + BaseAddress);
 
         // All range entries should lie in the function range.
         if (!CachedRange) {
@@ -1698,8 +1698,8 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
         }
 
         LinkedRanges.insert(
-            {Range.StartAddress + BaseAddress + CachedRange->Value,
-             Range.EndAddress + BaseAddress + CachedRange->Value});
+            {Range.StartAddress + BaseAddress + CachedRange->second,
+             Range.EndAddress + BaseAddress + CachedRange->second});
       }
     }
 
@@ -1802,7 +1802,7 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
   // in NewRows.
   std::vector<DWARFDebugLine::Row> Seq;
   const auto &FunctionRanges = Unit.getFunctionRanges();
-  std::optional<AddressRangeValuePair> CurrRange;
+  std::optional<std::pair<AddressRange, int64_t>> CurrRange;
 
   // FIXME: This logic is meant to generate exactly the same output as
   // Darwin's classic dsymutil. There is a nicer way to implement this
@@ -1821,13 +1821,13 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
     // it is marked as end_sequence in the input (because in that
     // case, the relocation offset is accurate and that entry won't
     // serve as the start of another function).
-    if (!CurrRange || !CurrRange->Range.contains(Row.Address.Address) ||
-        (Row.Address.Address == CurrRange->Range.end() && !Row.EndSequence)) {
+    if (!CurrRange || !CurrRange->first.contains(Row.Address.Address) ||
+        (Row.Address.Address == CurrRange->first.end() && !Row.EndSequence)) {
       // We just stepped out of a known range. Insert a end_sequence
       // corresponding to the end of the range.
       uint64_t StopAddress =
-          CurrRange ? CurrRange->Range.end() + CurrRange->Value : -1ULL;
-      CurrRange = FunctionRanges.getRangeThatContains(Row.Address.Address);
+          CurrRange ? CurrRange->first.end() + CurrRange->second : -1ULL;
+      CurrRange = FunctionRanges.getRangeValueThatContains(Row.Address.Address);
       if (!CurrRange) {
         if (StopAddress != -1ULL) {
           // Try harder by looking in the Address ranges map.
@@ -1836,9 +1836,9 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
           // for now do as dsymutil.
           // FIXME: Understand exactly what cases this addresses and
           // potentially remove it along with the Ranges map.
-          if (std::optional<AddressRangeValuePair> Range =
-                  Ranges.getRangeThatContains(Row.Address.Address))
-            StopAddress = Row.Address.Address + (*Range).Value;
+          if (std::optional<std::pair<AddressRange, int64_t>> Range =
+                  Ranges.getRangeValueThatContains(Row.Address.Address))
+            StopAddress = Row.Address.Address + (*Range).second;
         }
       }
       if (StopAddress != -1ULL && !Seq.empty()) {
@@ -1863,7 +1863,7 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
       continue;
 
     // Relocate row address and add it to the current sequence.
-    Row.Address.Address += CurrRange->Value;
+    Row.Address.Address += CurrRange->second;
     Seq.emplace_back(Row);
 
     if (Row.EndSequence)
@@ -2002,8 +2002,8 @@ void DWARFLinker::patchFrameInfoForObject(const DWARFFile &File,
     // the function entry point, thus we can't just lookup the address
     // in the debug map. Use the AddressInfo's range map to see if the FDE
     // describes something that we can relocate.
-    std::optional<AddressRangeValuePair> Range =
-        Ranges.getRangeThatContains(Loc);
+    std::optional<std::pair<AddressRange, int64_t>> Range =
+        Ranges.getRangeValueThatContains(Loc);
     if (!Range) {
       // The +4 is to account for the size of the InitialLength field itself.
       InputOffset = EntryOffset + InitialLength + 4;
@@ -2032,7 +2032,7 @@ void DWARFLinker::patchFrameInfoForObject(const DWARFFile &File,
     // fields that will get reconstructed by emitFDE().
     unsigned FDERemainingBytes = InitialLength - (4 + AddrSize);
     TheDwarfEmitter->emitFDE(IteratorInserted.first->getValue(), AddrSize,
-                             Loc + Range->Value,
+                             Loc + Range->second,
                              FrameData.substr(InputOffset, FDERemainingBytes));
     InputOffset += FDERemainingBytes;
   }
diff --git a/llvm/lib/DWARFLinker/DWARFStreamer.cpp b/llvm/lib/DWARFLinker/DWARFStreamer.cpp
index ae79e8cb9066..5cad267fd845 100644
--- a/llvm/lib/DWARFLinker/DWARFStreamer.cpp
+++ b/llvm/lib/DWARFLinker/DWARFStreamer.cpp
@@ -402,9 +402,10 @@ void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
   // Linked addresses might end up in a different order.
   // Build linked address ranges.
   AddressRanges LinkedRanges;
-  for (const AddressRangeValuePair &Range : FunctionRanges)
+  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++)
     LinkedRanges.insert(
-        {Range.Range.start() + Range.Value, Range.Range.end() + Range.Value});
+        {FunctionRanges[Idx].first.start() + FunctionRanges[Idx].second,
+         FunctionRanges[Idx].first.end() + FunctionRanges[Idx].second});
 
   if (!FunctionRanges.empty())
     emitDwarfDebugArangesTable(Unit, LinkedRanges);
diff --git a/llvm/lib/Object/ELFObjectFile.cpp b/llvm/lib/Object/ELFObjectFile.cpp
index ebc57bd04be7..c6d536188391 100644
--- a/llvm/lib/Object/ELFObjectFile.cpp
+++ b/llvm/lib/Object/ELFObjectFile.cpp
@@ -303,12 +303,7 @@ Expected<SubtargetFeatures> ELFObjectFileBase::getRISCVFeatures() const {
   std::optional<StringRef> Attr =
       Attributes.getAttributeString(RISCVAttrs::ARCH);
   if (Attr) {
-    // Suppress version checking for experimental extensions to prevent erroring
-    // when getting any unknown version of experimental extension.
-    auto ParseResult = RISCVISAInfo::parseArchString(
-        *Attr, /*EnableExperimentalExtension=*/true,
-        /*ExperimentalExtensionVersionCheck=*/false,
-        /*IgnoreUnknown=*/true);
+    auto ParseResult = RISCVISAInfo::parseNormalizedArchString(*Attr);
     if (!ParseResult)
       return ParseResult.takeError();
     auto &ISAInfo = *ParseResult;
diff --git a/llvm/lib/Support/AddressRanges.cpp b/llvm/lib/Support/AddressRanges.cpp
new file mode 100644
index 000000000000..187d5be00dae
--- /dev/null
+++ b/llvm/lib/Support/AddressRanges.cpp
@@ -0,0 +1,70 @@
+//===- AddressRanges.cpp ----------------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/AddressRanges.h"
+#include "llvm/ADT/STLExtras.h"
+#include <inttypes.h>
+
+using namespace llvm;
+
+AddressRanges::Collection::const_iterator
+AddressRanges::insert(AddressRange Range) {
+  if (Range.size() == 0)
+    return Ranges.end();
+
+  auto It = llvm::upper_bound(Ranges, Range);
+  auto It2 = It;
+  while (It2 != Ranges.end() && It2->start() <= Range.end())
+    ++It2;
+  if (It != It2) {
+    Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
+    It = Ranges.erase(It, It2);
+  }
+  if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
+    --It;
+    *It = {It->start(), std::max(It->end(), Range.end())};
+    return It;
+  }
+
+  return Ranges.insert(It, Range);
+}
+
+AddressRanges::Collection::const_iterator
+AddressRanges::find(uint64_t Addr) const {
+  auto It = std::partition_point(
+      Ranges.begin(), Ranges.end(),
+      [=](const AddressRange &R) { return R.start() <= Addr; });
+
+  if (It == Ranges.begin())
+    return Ranges.end();
+
+  --It;
+  if (Addr >= It->end())
+    return Ranges.end();
+
+  return It;
+}
+
+AddressRanges::Collection::const_iterator
+AddressRanges::find(AddressRange Range) const {
+  if (Range.size() == 0)
+    return Ranges.end();
+
+  auto It = std::partition_point(
+      Ranges.begin(), Ranges.end(),
+      [=](const AddressRange &R) { return R.start() <= Range.start(); });
+
+  if (It == Ranges.begin())
+    return Ranges.end();
+
+  --It;
+  if (Range.end() > It->end())
+    return Ranges.end();
+
+  return It;
+}
diff --git a/llvm/lib/Support/RISCVISAInfo.cpp b/llvm/lib/Support/RISCVISAInfo.cpp
index b14fe1358d1f..7cb1147d4265 100644
--- a/llvm/lib/Support/RISCVISAInfo.cpp
+++ b/llvm/lib/Support/RISCVISAInfo.cpp
@@ -1060,6 +1060,8 @@ std::vector<std::string> RISCVISAInfo::toFeatureVector() const {
     std::string ExtName = Ext.first;
     if (ExtName == "i") // i is not recognized in clang -cc1
       continue;
+    if (!isSupportedExtension(ExtName))
+      continue;
     std::string Feature = isExperimentalExtension(ExtName)
                               ? "+experimental-" + ExtName
                               : "+" + ExtName;
diff --git a/llvm/lib/Target/ARM/ARMFrameLowering.cpp b/llvm/lib/Target/ARM/ARMFrameLowering.cpp
index 5fa7068c89eb..724705c25e3a 100644
--- a/llvm/lib/Target/ARM/ARMFrameLowering.cpp
+++ b/llvm/lib/Target/ARM/ARMFrameLowering.cpp
@@ -357,6 +357,34 @@ static MachineBasicBlock::iterator insertSEH(MachineBasicBlock::iterator MBBI,
               .setMIFlags(Flags);
     break;
 
+  case ARM::t2STR_PRE:
+    if (MBBI->getOperand(0).getReg() == ARM::SP &&
+        MBBI->getOperand(2).getReg() == ARM::SP &&
+        MBBI->getOperand(3).getImm() == -4) {
+      unsigned Reg = RegInfo->getSEHRegNum(MBBI->getOperand(1).getReg());
+      MIB = BuildMI(MF, DL, TII.get(ARM::SEH_SaveRegs))
+                .addImm(1ULL << Reg)
+                .addImm(/*Wide=*/1)
+                .setMIFlags(Flags);
+    } else {
+      report_fatal_error("No matching SEH Opcode for t2STR_PRE");
+    }
+    break;
+
+  case ARM::t2LDR_POST:
+    if (MBBI->getOperand(1).getReg() == ARM::SP &&
+        MBBI->getOperand(2).getReg() == ARM::SP &&
+        MBBI->getOperand(3).getImm() == 4) {
+      unsigned Reg = RegInfo->getSEHRegNum(MBBI->getOperand(0).getReg());
+      MIB = BuildMI(MF, DL, TII.get(ARM::SEH_SaveRegs))
+                .addImm(1ULL << Reg)
+                .addImm(/*Wide=*/1)
+                .setMIFlags(Flags);
+    } else {
+      report_fatal_error("No matching SEH Opcode for t2LDR_POST");
+    }
+    break;
+
   case ARM::t2LDMIA_RET:
   case ARM::t2LDMIA_UPD:
   case ARM::t2STMDB_UPD: {
diff --git a/llvm/lib/Target/RISCV/RISCVISelLowering.cpp b/llvm/lib/Target/RISCV/RISCVISelLowering.cpp
index 6eea169f8919..a1dc6a0cd2c1 100644
--- a/llvm/lib/Target/RISCV/RISCVISelLowering.cpp
+++ b/llvm/lib/Target/RISCV/RISCVISelLowering.cpp
@@ -4540,6 +4540,9 @@ SDValue RISCVTargetLowering::lowerGlobalTLSAddress(SDValue Op,
   GlobalAddressSDNode *N = cast<GlobalAddressSDNode>(Op);
   assert(N->getOffset() == 0 && "unexpected offset in global node");
 
+  if (DAG.getTarget().useEmulatedTLS())
+    return LowerToTLSEmulatedModel(N, DAG);
+
   TLSModel::Model Model = getTargetMachine().getTLSModel(N->getGlobal());
 
   if (DAG.getMachineFunction().getFunction().getCallingConv() ==
diff --git a/llvm/lib/Target/Sparc/MCTargetDesc/SparcInstPrinter.cpp b/llvm/lib/Target/Sparc/MCTargetDesc/SparcInstPrinter.cpp
index fb22ddd91ba0..14c0e276a11b 100644
--- a/llvm/lib/Target/Sparc/MCTargetDesc/SparcInstPrinter.cpp
+++ b/llvm/lib/Target/Sparc/MCTargetDesc/SparcInstPrinter.cpp
@@ -178,6 +178,8 @@ void SparcInstPrinter::printCCOperand(const MCInst *MI, int opNum,
   default: break;
   case SP::FBCOND:
   case SP::FBCONDA:
+  case SP::FBCOND_V9:
+  case SP::FBCONDA_V9:
   case SP::BPFCC:
   case SP::BPFCCA:
   case SP::BPFCCNT:
diff --git a/llvm/lib/Target/Sparc/SparcInstrInfo.cpp b/llvm/lib/Target/Sparc/SparcInstrInfo.cpp
index 63f662c41f93..a3a09a36f1dd 100644
--- a/llvm/lib/Target/Sparc/SparcInstrInfo.cpp
+++ b/llvm/lib/Target/Sparc/SparcInstrInfo.cpp
@@ -28,6 +28,10 @@ using namespace llvm;
 #define GET_INSTRINFO_CTOR_DTOR
 #include "SparcGenInstrInfo.inc"
 
+static cl::opt<unsigned> BPccDisplacementBits(
+    "sparc-bpcc-offset-bits", cl::Hidden, cl::init(19),
+    cl::desc("Restrict range of BPcc/FBPfcc instructions (DEBUG)"));
+
 // Pin the vtable to this file.
 void SparcInstrInfo::anchor() {}
 
@@ -73,11 +77,6 @@ unsigned SparcInstrInfo::isStoreToStackSlot(const MachineInstr &MI,
   return 0;
 }
 
-static bool IsIntegerCC(unsigned CC)
-{
-  return  (CC <= SPCC::ICC_VC);
-}
-
 static SPCC::CondCodes GetOppositeBranchCondition(SPCC::CondCodes CC)
 {
   switch(CC) {
@@ -155,9 +154,7 @@ static SPCC::CondCodes GetOppositeBranchCondition(SPCC::CondCodes CC)
   llvm_unreachable("Invalid cond code");
 }
 
-static bool isUncondBranchOpcode(int Opc) {
-  return Opc == SP::BA || Opc == SP::BPA;
-}
+static bool isUncondBranchOpcode(int Opc) { return Opc == SP::BA; }
 
 static bool isI32CondBranchOpcode(int Opc) {
   return Opc == SP::BCOND || Opc == SP::BPICC || Opc == SP::BPICCA ||
@@ -169,7 +166,10 @@ static bool isI64CondBranchOpcode(int Opc) {
          Opc == SP::BPXCCANT;
 }
 
-static bool isFCondBranchOpcode(int Opc) { return Opc == SP::FBCOND; }
+static bool isFCondBranchOpcode(int Opc) {
+  return Opc == SP::FBCOND || Opc == SP::FBCONDA || Opc == SP::FBCOND_V9 ||
+         Opc == SP::FBCONDA_V9;
+}
 
 static bool isCondBranchOpcode(int Opc) {
   return isI32CondBranchOpcode(Opc) || isI64CondBranchOpcode(Opc) ||
@@ -193,6 +193,34 @@ static void parseCondBranch(MachineInstr *LastInst, MachineBasicBlock *&Target,
   Target = LastInst->getOperand(0).getMBB();
 }
 
+MachineBasicBlock *
+SparcInstrInfo::getBranchDestBlock(const MachineInstr &MI) const {
+  switch (MI.getOpcode()) {
+  default:
+      llvm_unreachable("unexpected opcode!");
+  case SP::BA:
+  case SP::BCOND:
+  case SP::BCONDA:
+  case SP::FBCOND:
+  case SP::FBCONDA:
+  case SP::BPICC:
+  case SP::BPICCA:
+  case SP::BPICCNT:
+  case SP::BPICCANT:
+  case SP::BPXCC:
+  case SP::BPXCCA:
+  case SP::BPXCCNT:
+  case SP::BPXCCANT:
+  case SP::BPFCC:
+  case SP::BPFCCA:
+  case SP::BPFCCNT:
+  case SP::BPFCCANT:
+  case SP::FBCOND_V9:
+  case SP::FBCONDA_V9:
+      return MI.getOperand(0).getMBB();
+  }
+}
+
 bool SparcInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
                                    MachineBasicBlock *&TBB,
                                    MachineBasicBlock *&FBB,
@@ -285,36 +313,37 @@ unsigned SparcInstrInfo::insertBranch(MachineBasicBlock &MBB,
   assert(TBB && "insertBranch must not be told to insert a fallthrough");
   assert((Cond.size() <= 2) &&
          "Sparc branch conditions should have at most two components!");
-  assert(!BytesAdded && "code size not handled");
 
   if (Cond.empty()) {
     assert(!FBB && "Unconditional branch with multiple successors!");
-    BuildMI(&MBB, DL, get(Subtarget.isV9() ? SP::BPA : SP::BA)).addMBB(TBB);
+    BuildMI(&MBB, DL, get(SP::BA)).addMBB(TBB);
+    if (BytesAdded)
+      *BytesAdded = 8;
     return 1;
   }
 
   // Conditional branch
   unsigned Opc = Cond[0].getImm();
   unsigned CC = Cond[1].getImm();
+  BuildMI(&MBB, DL, get(Opc)).addMBB(TBB).addImm(CC);
 
-  if (IsIntegerCC(CC)) {
-    BuildMI(&MBB, DL, get(Opc)).addMBB(TBB).addImm(CC);
-  } else {
-    BuildMI(&MBB, DL, get(SP::FBCOND)).addMBB(TBB).addImm(CC);
-  }
-  if (!FBB)
+  if (!FBB) {
+    if (BytesAdded)
+      *BytesAdded = 8;
     return 1;
+  }
 
-  BuildMI(&MBB, DL, get(Subtarget.isV9() ? SP::BPA : SP::BA)).addMBB(FBB);
+  BuildMI(&MBB, DL, get(SP::BA)).addMBB(FBB);
+  if (BytesAdded)
+    *BytesAdded = 16;
   return 2;
 }
 
 unsigned SparcInstrInfo::removeBranch(MachineBasicBlock &MBB,
                                       int *BytesRemoved) const {
-  assert(!BytesRemoved && "code size not handled");
-
   MachineBasicBlock::iterator I = MBB.end();
   unsigned Count = 0;
+  int Removed = 0;
   while (I != MBB.begin()) {
     --I;
 
@@ -325,10 +354,14 @@ unsigned SparcInstrInfo::removeBranch(MachineBasicBlock &MBB,
         !isUncondBranchOpcode(I->getOpcode()))
       break; // Not a branch
 
+    Removed += getInstSizeInBytes(*I);
     I->eraseFromParent();
     I = MBB.end();
     ++Count;
   }
+
+  if (BytesRemoved)
+    *BytesRemoved = Removed;
   return Count;
 }
 
@@ -340,6 +373,37 @@ bool SparcInstrInfo::reverseBranchCondition(
   return false;
 }
 
+bool SparcInstrInfo::isBranchOffsetInRange(unsigned BranchOpc,
+                                           int64_t Offset) const {
+  assert((Offset & 0b11) == 0 && "Malformed branch offset");
+  switch (BranchOpc) {
+  case SP::BA:
+  case SP::BCOND:
+  case SP::BCONDA:
+  case SP::FBCOND:
+  case SP::FBCONDA:
+    return isIntN(22, Offset >> 2);
+
+  case SP::BPICC:
+  case SP::BPICCA:
+  case SP::BPICCNT:
+  case SP::BPICCANT:
+  case SP::BPXCC:
+  case SP::BPXCCA:
+  case SP::BPXCCNT:
+  case SP::BPXCCANT:
+  case SP::BPFCC:
+  case SP::BPFCCA:
+  case SP::BPFCCNT:
+  case SP::BPFCCANT:
+  case SP::FBCOND_V9:
+  case SP::FBCONDA_V9:
+    return isIntN(BPccDisplacementBits, Offset >> 2);
+  }
+
+  llvm_unreachable("Unknown branch instruction!");
+}
+
 void SparcInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator I,
                                  const DebugLoc &DL, MCRegister DestReg,
@@ -530,6 +594,23 @@ Register SparcInstrInfo::getGlobalBaseReg(MachineFunction *MF) const {
   return GlobalBaseReg;
 }
 
+unsigned SparcInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
+  unsigned Opcode = MI.getOpcode();
+
+  if (MI.isInlineAsm()) {
+    const MachineFunction *MF = MI.getParent()->getParent();
+    const char *AsmStr = MI.getOperand(0).getSymbolName();
+    return getInlineAsmLength(AsmStr, *MF->getTarget().getMCAsmInfo());
+  }
+
+  // If the instruction has a delay slot, be conservative and also include
+  // it for sizing purposes. This is done so that the BranchRelaxation pass
+  // will not mistakenly mark out-of-range branches as in-range.
+  if (MI.hasDelaySlot())
+    return get(Opcode).getSize() * 2;
+  return get(Opcode).getSize();
+}
+
 bool SparcInstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
   switch (MI.getOpcode()) {
   case TargetOpcode::LOAD_STACK_GUARD: {
diff --git a/llvm/lib/Target/Sparc/SparcInstrInfo.h b/llvm/lib/Target/Sparc/SparcInstrInfo.h
index 39cf791c2173..7056d6babe17 100644
--- a/llvm/lib/Target/Sparc/SparcInstrInfo.h
+++ b/llvm/lib/Target/Sparc/SparcInstrInfo.h
@@ -64,6 +64,8 @@ public:
   unsigned isStoreToStackSlot(const MachineInstr &MI,
                               int &FrameIndex) const override;
 
+  MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
+
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
@@ -80,6 +82,9 @@ public:
   bool
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 
+  /// Determine if the branch target is in range.
+  bool isBranchOffsetInRange(unsigned BranchOpc, int64_t Offset) const override;
+
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                    const DebugLoc &DL, MCRegister DestReg, MCRegister SrcReg,
                    bool KillSrc) const override;
@@ -99,6 +104,10 @@ public:
 
   Register getGlobalBaseReg(MachineFunction *MF) const;
 
+  /// GetInstSize - Return the number of bytes of code the specified
+  /// instruction may be.  This returns the maximum number of bytes.
+  unsigned getInstSizeInBytes(const MachineInstr &MI) const override;
+
   // Lower pseudo instructions after register allocation.
   bool expandPostRAPseudo(MachineInstr &MI) const override;
 };
diff --git a/llvm/lib/Target/Sparc/SparcInstrInfo.td b/llvm/lib/Target/Sparc/SparcInstrInfo.td
index 2c45a7218d04..2e95bc10337a 100644
--- a/llvm/lib/Target/Sparc/SparcInstrInfo.td
+++ b/llvm/lib/Target/Sparc/SparcInstrInfo.td
@@ -850,15 +850,8 @@ class BranchPredictAlways<dag ins, string asmstr, list<dag> pattern>
   : F2_3<0b001, 0, 1, (outs), ins, asmstr, pattern>;
 }
 
-let cond = 8 in {
-  // If we're compiling for v9, prefer BPA rather than BA
-  // TODO: Disallow BA emission when FeatureV8Deprecated isn't enabled
-  let Predicates = [HasV9], cc = 0b00 in
-    def BPA : BranchPredictAlways<(ins bprtarget:$imm19),
-      "ba %icc, $imm19", [(br bb:$imm19)]>;
-
+let cond = 8 in
   def BA : BranchAlways<(ins brtarget:$imm22), "ba $imm22", [(br bb:$imm22)]>;
-}
 
 let isBranch = 1, isTerminator = 1, hasDelaySlot = 1 in {
 
diff --git a/llvm/lib/Target/Sparc/SparcTargetMachine.cpp b/llvm/lib/Target/Sparc/SparcTargetMachine.cpp
index 58faaafc29d6..1dbe5c563359 100644
--- a/llvm/lib/Target/Sparc/SparcTargetMachine.cpp
+++ b/llvm/lib/Target/Sparc/SparcTargetMachine.cpp
@@ -32,6 +32,10 @@ extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeSparcTarget() {
   initializeSparcDAGToDAGISelPass(PR);
 }
 
+static cl::opt<bool>
+    BranchRelaxation("sparc-enable-branch-relax", cl::Hidden, cl::init(true),
+                     cl::desc("Relax out of range conditional branches"));
+
 static std::string computeDataLayout(const Triple &T, bool is64Bit) {
   // Sparc is typically big endian, but some are little.
   std::string Ret = T.getArch() == Triple::sparcel ? "e" : "E";
@@ -182,6 +186,9 @@ bool SparcPassConfig::addInstSelector() {
 }
 
 void SparcPassConfig::addPreEmitPass(){
+  if (BranchRelaxation)
+    addPass(&BranchRelaxationPassID);
+
   addPass(createSparcDelaySlotFillerPass());
 
   if (this->getSparcTargetMachine().getSubtargetImpl()->insertNOPLoad())
diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index 31cdd2ee56b9..b2ed95b05e04 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -2930,7 +2930,8 @@ void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
     return;
 
   unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
-  if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
+  if (BitWidth == OldLI.getType()->getScalarSizeInBits() &&
+      !getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
     MDNode *NN = MDNode::get(OldLI.getContext(), std::nullopt);
     NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
   }