[committed] libstdc++: Define C++26 saturation arithmetic functions (P0543R3)

Message ID 20231117153138.1510158-1-jwakely@redhat.com
State Committed
Headers
Series [committed] libstdc++: Define C++26 saturation arithmetic functions (P0543R3) |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 warning Patch is already merged
linaro-tcwg-bot/tcwg_gcc_build--master-arm warning Patch is already merged

Commit Message

Jonathan Wakely Nov. 17, 2023, 3:29 p.m. UTC
  Tested x86_64-linux. Pushed to trunk.

GCC generates better code for add_sat<unsigned> if we use:

unsigned z = x + y;
z |= -(z < x);
return z;

If the compiler can't be improved we should consider using that instead
of __builtin_add_overflow.


-- >8 --


This was approved for C++26 last week at the WG21 meeting in Kona.

libstdc++-v3/ChangeLog:

	* include/Makefile.am: Add new header.
	* include/Makefile.in: Regenerate.
	* include/bits/version.def (saturation_arithmetic): Define.
	* include/bits/version.h: Regenerate.
	* include/std/numeric: Include new header.
	* include/bits/sat_arith.h: New file.
	* testsuite/26_numerics/saturation/add.cc: New test.
	* testsuite/26_numerics/saturation/cast.cc: New test.
	* testsuite/26_numerics/saturation/div.cc: New test.
	* testsuite/26_numerics/saturation/mul.cc: New test.
	* testsuite/26_numerics/saturation/sub.cc: New test.
	* testsuite/26_numerics/saturation/version.cc: New test.
---
 libstdc++-v3/include/Makefile.am              |   1 +
 libstdc++-v3/include/Makefile.in              |   1 +
 libstdc++-v3/include/bits/sat_arith.h         | 148 ++++++++++++++++++
 libstdc++-v3/include/bits/version.def         |   8 +
 libstdc++-v3/include/bits/version.h           |  11 ++
 libstdc++-v3/include/std/numeric              |   5 +
 .../testsuite/26_numerics/saturation/add.cc   |  73 +++++++++
 .../testsuite/26_numerics/saturation/cast.cc  |  24 +++
 .../testsuite/26_numerics/saturation/div.cc   |  45 ++++++
 .../testsuite/26_numerics/saturation/mul.cc   |  34 ++++
 .../testsuite/26_numerics/saturation/sub.cc   |  86 ++++++++++
 .../26_numerics/saturation/version.cc         |  19 +++
 12 files changed, 455 insertions(+)
 create mode 100644 libstdc++-v3/include/bits/sat_arith.h
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/add.cc
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/cast.cc
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/div.cc
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/mul.cc
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/sub.cc
 create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/version.cc
  

Comments

Daniel Krügler Nov. 17, 2023, 5:01 p.m. UTC | #1
Am Fr., 17. Nov. 2023 um 16:32 Uhr schrieb Jonathan Wakely <jwakely@redhat.com>:
>
> Tested x86_64-linux. Pushed to trunk.
>
> GCC generates better code for add_sat<unsigned> if we use:
>
> unsigned z = x + y;
> z |= -(z < x);
> return z;
>
> If the compiler can't be improved we should consider using that instead
> of __builtin_add_overflow.
>
>
> -- >8 --
>
>
> This was approved for C++26 last week at the WG21 meeting in Kona.
>
> libstdc++-v3/ChangeLog:
>
>         * include/Makefile.am: Add new header.
>         * include/Makefile.in: Regenerate.
>         * include/bits/version.def (saturation_arithmetic): Define.
>         * include/bits/version.h: Regenerate.
>         * include/std/numeric: Include new header.
>         * include/bits/sat_arith.h: New file.
>         * testsuite/26_numerics/saturation/add.cc: New test.
>         * testsuite/26_numerics/saturation/cast.cc: New test.
>         * testsuite/26_numerics/saturation/div.cc: New test.
>         * testsuite/26_numerics/saturation/mul.cc: New test.
>         * testsuite/26_numerics/saturation/sub.cc: New test.
>         * testsuite/26_numerics/saturation/version.cc: New test.
> ---
>  libstdc++-v3/include/Makefile.am              |   1 +
>  libstdc++-v3/include/Makefile.in              |   1 +
>  libstdc++-v3/include/bits/sat_arith.h         | 148 ++++++++++++++++++
>  libstdc++-v3/include/bits/version.def         |   8 +
>  libstdc++-v3/include/bits/version.h           |  11 ++
>  libstdc++-v3/include/std/numeric              |   5 +
>  .../testsuite/26_numerics/saturation/add.cc   |  73 +++++++++
>  .../testsuite/26_numerics/saturation/cast.cc  |  24 +++
>  .../testsuite/26_numerics/saturation/div.cc   |  45 ++++++
>  .../testsuite/26_numerics/saturation/mul.cc   |  34 ++++
>  .../testsuite/26_numerics/saturation/sub.cc   |  86 ++++++++++
>  .../26_numerics/saturation/version.cc         |  19 +++
>  12 files changed, 455 insertions(+)
>  create mode 100644 libstdc++-v3/include/bits/sat_arith.h
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/add.cc
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/cast.cc
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/div.cc
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/mul.cc
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/sub.cc
>  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/version.cc
>
> diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
> index dab9f720cbb..17d9d9cec31 100644
> --- a/libstdc++-v3/include/Makefile.am
> +++ b/libstdc++-v3/include/Makefile.am
> @@ -142,6 +142,7 @@ bits_freestanding = \
>         ${bits_srcdir}/ranges_uninitialized.h \
>         ${bits_srcdir}/ranges_util.h \
>         ${bits_srcdir}/refwrap.h \
> +       ${bits_srcdir}/sat_arith.h \
>         ${bits_srcdir}/stl_algo.h \
>         ${bits_srcdir}/stl_algobase.h \
>         ${bits_srcdir}/stl_construct.h \
> diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
> index 4f7ab2dfbab..f038af709cc 100644
> --- a/libstdc++-v3/include/Makefile.in
> +++ b/libstdc++-v3/include/Makefile.in
> @@ -497,6 +497,7 @@ bits_freestanding = \
>         ${bits_srcdir}/ranges_uninitialized.h \
>         ${bits_srcdir}/ranges_util.h \
>         ${bits_srcdir}/refwrap.h \
> +       ${bits_srcdir}/sat_arith.h \
>         ${bits_srcdir}/stl_algo.h \
>         ${bits_srcdir}/stl_algobase.h \
>         ${bits_srcdir}/stl_construct.h \
> diff --git a/libstdc++-v3/include/bits/sat_arith.h b/libstdc++-v3/include/bits/sat_arith.h
> new file mode 100644
> index 00000000000..71793467984
> --- /dev/null
> +++ b/libstdc++-v3/include/bits/sat_arith.h
> @@ -0,0 +1,148 @@
> +// Saturation arithmetic -*- C++ -*-
> +
> +// Copyright The GNU Toolchain Authors.
> +//
> +// This file is part of the GNU ISO C++ Library.  This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +// GNU General Public License for more details.
> +
> +// Under Section 7 of GPL version 3, you are granted additional
> +// permissions described in the GCC Runtime Library Exception, version
> +// 3.1, as published by the Free Software Foundation.
> +
> +// You should have received a copy of the GNU General Public License and
> +// a copy of the GCC Runtime Library Exception along with this program;
> +// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @file include/bits/sat_arith.h
> + *  This is an internal header file, included by other library headers.
> + *  Do not attempt to use it directly. @headername{numeric}
> + */
> +
> +#ifndef _GLIBCXX_SAT_ARITH_H
> +#define _GLIBCXX_SAT_ARITH_H 1
> +
> +#pragma GCC system_header
> +
> +#include <bits/version.h>
> +
> +#ifdef __glibcxx_saturation_arithmetic // C++ >= 26
> +
> +#include <concepts>
> +#include <ext/numeric_traits.h>
> +
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> +
> +  /// Add two integers, with saturation in case of overflow.
> +  template<typename _Tp> requires __is_standard_integer<_Tp>::value
> +    constexpr _Tp
> +    add_sat(_Tp __x, _Tp __y) noexcept
> +    {
> +      _Tp __z;
> +      if (!__builtin_add_overflow(__x, __y, &__z))
> +       return __z;
> +      if constexpr (is_unsigned_v<_Tp>)
> +       return __gnu_cxx::__int_traits<_Tp>::__max;
> +      else if (__x < 0)
> +       return __gnu_cxx::__int_traits<_Tp>::__min;

My apologies, but why does the sign of x decide the direction of the
result, shouldn't that be the sign of the returned value of z?

- Daniel
  
Jonathan Wakely Nov. 17, 2023, 5:31 p.m. UTC | #2
On Fri, 17 Nov 2023 at 17:01, Daniel Krügler <daniel.kruegler@gmail.com> wrote:
>
> Am Fr., 17. Nov. 2023 um 16:32 Uhr schrieb Jonathan Wakely <jwakely@redhat.com>:
> >
> > Tested x86_64-linux. Pushed to trunk.
> >
> > GCC generates better code for add_sat<unsigned> if we use:
> >
> > unsigned z = x + y;
> > z |= -(z < x);
> > return z;
> >
> > If the compiler can't be improved we should consider using that instead
> > of __builtin_add_overflow.
> >
> >
> > -- >8 --
> >
> >
> > This was approved for C++26 last week at the WG21 meeting in Kona.
> >
> > libstdc++-v3/ChangeLog:
> >
> >         * include/Makefile.am: Add new header.
> >         * include/Makefile.in: Regenerate.
> >         * include/bits/version.def (saturation_arithmetic): Define.
> >         * include/bits/version.h: Regenerate.
> >         * include/std/numeric: Include new header.
> >         * include/bits/sat_arith.h: New file.
> >         * testsuite/26_numerics/saturation/add.cc: New test.
> >         * testsuite/26_numerics/saturation/cast.cc: New test.
> >         * testsuite/26_numerics/saturation/div.cc: New test.
> >         * testsuite/26_numerics/saturation/mul.cc: New test.
> >         * testsuite/26_numerics/saturation/sub.cc: New test.
> >         * testsuite/26_numerics/saturation/version.cc: New test.
> > ---
> >  libstdc++-v3/include/Makefile.am              |   1 +
> >  libstdc++-v3/include/Makefile.in              |   1 +
> >  libstdc++-v3/include/bits/sat_arith.h         | 148 ++++++++++++++++++
> >  libstdc++-v3/include/bits/version.def         |   8 +
> >  libstdc++-v3/include/bits/version.h           |  11 ++
> >  libstdc++-v3/include/std/numeric              |   5 +
> >  .../testsuite/26_numerics/saturation/add.cc   |  73 +++++++++
> >  .../testsuite/26_numerics/saturation/cast.cc  |  24 +++
> >  .../testsuite/26_numerics/saturation/div.cc   |  45 ++++++
> >  .../testsuite/26_numerics/saturation/mul.cc   |  34 ++++
> >  .../testsuite/26_numerics/saturation/sub.cc   |  86 ++++++++++
> >  .../26_numerics/saturation/version.cc         |  19 +++
> >  12 files changed, 455 insertions(+)
> >  create mode 100644 libstdc++-v3/include/bits/sat_arith.h
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/add.cc
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/cast.cc
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/div.cc
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/mul.cc
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/sub.cc
> >  create mode 100644 libstdc++-v3/testsuite/26_numerics/saturation/version.cc
> >
> > diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
> > index dab9f720cbb..17d9d9cec31 100644
> > --- a/libstdc++-v3/include/Makefile.am
> > +++ b/libstdc++-v3/include/Makefile.am
> > @@ -142,6 +142,7 @@ bits_freestanding = \
> >         ${bits_srcdir}/ranges_uninitialized.h \
> >         ${bits_srcdir}/ranges_util.h \
> >         ${bits_srcdir}/refwrap.h \
> > +       ${bits_srcdir}/sat_arith.h \
> >         ${bits_srcdir}/stl_algo.h \
> >         ${bits_srcdir}/stl_algobase.h \
> >         ${bits_srcdir}/stl_construct.h \
> > diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
> > index 4f7ab2dfbab..f038af709cc 100644
> > --- a/libstdc++-v3/include/Makefile.in
> > +++ b/libstdc++-v3/include/Makefile.in
> > @@ -497,6 +497,7 @@ bits_freestanding = \
> >         ${bits_srcdir}/ranges_uninitialized.h \
> >         ${bits_srcdir}/ranges_util.h \
> >         ${bits_srcdir}/refwrap.h \
> > +       ${bits_srcdir}/sat_arith.h \
> >         ${bits_srcdir}/stl_algo.h \
> >         ${bits_srcdir}/stl_algobase.h \
> >         ${bits_srcdir}/stl_construct.h \
> > diff --git a/libstdc++-v3/include/bits/sat_arith.h b/libstdc++-v3/include/bits/sat_arith.h
> > new file mode 100644
> > index 00000000000..71793467984
> > --- /dev/null
> > +++ b/libstdc++-v3/include/bits/sat_arith.h
> > @@ -0,0 +1,148 @@
> > +// Saturation arithmetic -*- C++ -*-
> > +
> > +// Copyright The GNU Toolchain Authors.
> > +//
> > +// This file is part of the GNU ISO C++ Library.  This library is free
> > +// software; you can redistribute it and/or modify it under the
> > +// terms of the GNU General Public License as published by the
> > +// Free Software Foundation; either version 3, or (at your option)
> > +// any later version.
> > +
> > +// This library is distributed in the hope that it will be useful,
> > +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> > +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> > +// GNU General Public License for more details.
> > +
> > +// Under Section 7 of GPL version 3, you are granted additional
> > +// permissions described in the GCC Runtime Library Exception, version
> > +// 3.1, as published by the Free Software Foundation.
> > +
> > +// You should have received a copy of the GNU General Public License and
> > +// a copy of the GCC Runtime Library Exception along with this program;
> > +// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
> > +// <http://www.gnu.org/licenses/>.
> > +
> > +/** @file include/bits/sat_arith.h
> > + *  This is an internal header file, included by other library headers.
> > + *  Do not attempt to use it directly. @headername{numeric}
> > + */
> > +
> > +#ifndef _GLIBCXX_SAT_ARITH_H
> > +#define _GLIBCXX_SAT_ARITH_H 1
> > +
> > +#pragma GCC system_header
> > +
> > +#include <bits/version.h>
> > +
> > +#ifdef __glibcxx_saturation_arithmetic // C++ >= 26
> > +
> > +#include <concepts>
> > +#include <ext/numeric_traits.h>
> > +
> > +namespace std _GLIBCXX_VISIBILITY(default)
> > +{
> > +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> > +
> > +  /// Add two integers, with saturation in case of overflow.
> > +  template<typename _Tp> requires __is_standard_integer<_Tp>::value
> > +    constexpr _Tp
> > +    add_sat(_Tp __x, _Tp __y) noexcept
> > +    {
> > +      _Tp __z;
> > +      if (!__builtin_add_overflow(__x, __y, &__z))
> > +       return __z;
> > +      if constexpr (is_unsigned_v<_Tp>)
> > +       return __gnu_cxx::__int_traits<_Tp>::__max;
> > +      else if (__x < 0)
> > +       return __gnu_cxx::__int_traits<_Tp>::__min;
>
> My apologies, but why does the sign of x decide the direction of the
> result, shouldn't that be the sign of the returned value of z?

z is incorrect at this point, it only has the correct value if no
overflow occurred. But we know that an overflow occurred because the
built-in returned true.

We need to determine whether the overflow was positive, i.e. greater
than numeric_limits<T>::max(), or negative, i.e. lower than
numeric_limits<T>::min(). For unsigned types, it must have been a
positive overflow, because neither value is negative so that's easy.

If x is negative, then there is no possible y that can cause a
positive overflow. If we consider Tp==int, then the maximum y is
INT_MAX, so if x is negative, x+INT_MAX < INT_MAX. So if x is
negative, we must have had a negative overflow, and so the result
saturates to INT_MIN.

If x is positive, there is no possible y that can cause a negative
overflow. The minimum y is INT_MIN, and so if x is positive, x +
INT_MIN > INT_MIN. So if x is positive, we must have had a positive
overflow.

(And x can't be zero, because 0+y would not overflow).
  
Daniel Krügler Nov. 17, 2023, 5:37 p.m. UTC | #3
Am Fr., 17. Nov. 2023 um 18:31 Uhr schrieb Jonathan Wakely <jwakely@redhat.com>:
>
> On Fri, 17 Nov 2023 at 17:01, Daniel Krügler <daniel.kruegler@gmail.com> wrote:
> >
[..]
> > > +
> > > +namespace std _GLIBCXX_VISIBILITY(default)
> > > +{
> > > +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> > > +
> > > +  /// Add two integers, with saturation in case of overflow.
> > > +  template<typename _Tp> requires __is_standard_integer<_Tp>::value
> > > +    constexpr _Tp
> > > +    add_sat(_Tp __x, _Tp __y) noexcept
> > > +    {
> > > +      _Tp __z;
> > > +      if (!__builtin_add_overflow(__x, __y, &__z))
> > > +       return __z;
> > > +      if constexpr (is_unsigned_v<_Tp>)
> > > +       return __gnu_cxx::__int_traits<_Tp>::__max;
> > > +      else if (__x < 0)
> > > +       return __gnu_cxx::__int_traits<_Tp>::__min;
> >
> > My apologies, but why does the sign of x decide the direction of the
> > result, shouldn't that be the sign of the returned value of z?
>
> z is incorrect at this point, it only has the correct value if no
> overflow occurred. But we know that an overflow occurred because the
> built-in returned true.
>
> We need to determine whether the overflow was positive, i.e. greater
> than numeric_limits<T>::max(), or negative, i.e. lower than
> numeric_limits<T>::min(). For unsigned types, it must have been a
> positive overflow, because neither value is negative so that's easy.
>
> If x is negative, then there is no possible y that can cause a
> positive overflow. If we consider Tp==int, then the maximum y is
> INT_MAX, so if x is negative, x+INT_MAX < INT_MAX. So if x is
> negative, we must have had a negative overflow, and so the result
> saturates to INT_MIN.
>
> If x is positive, there is no possible y that can cause a negative
> overflow. The minimum y is INT_MIN, and so if x is positive, x +
> INT_MIN > INT_MIN. So if x is positive, we must have had a positive
> overflow.
>
> (And x can't be zero, because 0+y would not overflow).

Ah right, thanks.

- Daniel
  
Jonathan Wakely Nov. 17, 2023, 10 p.m. UTC | #4
On Fri, 17 Nov 2023 at 15:32, Jonathan Wakely <jwakely@redhat.com> wrote:
>
> Tested x86_64-linux. Pushed to trunk.
>
> GCC generates better code for add_sat<unsigned> if we use:
>
> unsigned z = x + y;
> z |= -(z < x);
> return z;
>
> If the compiler can't be improved we should consider using that instead
> of __builtin_add_overflow.

I reported PR 112600 for the missed optimization. I added an optimized
sub_sat<unsigned> there as well.
  

Patch

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index dab9f720cbb..17d9d9cec31 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -142,6 +142,7 @@  bits_freestanding = \
 	${bits_srcdir}/ranges_uninitialized.h \
 	${bits_srcdir}/ranges_util.h \
 	${bits_srcdir}/refwrap.h \
+	${bits_srcdir}/sat_arith.h \
 	${bits_srcdir}/stl_algo.h \
 	${bits_srcdir}/stl_algobase.h \
 	${bits_srcdir}/stl_construct.h \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index 4f7ab2dfbab..f038af709cc 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -497,6 +497,7 @@  bits_freestanding = \
 	${bits_srcdir}/ranges_uninitialized.h \
 	${bits_srcdir}/ranges_util.h \
 	${bits_srcdir}/refwrap.h \
+	${bits_srcdir}/sat_arith.h \
 	${bits_srcdir}/stl_algo.h \
 	${bits_srcdir}/stl_algobase.h \
 	${bits_srcdir}/stl_construct.h \
diff --git a/libstdc++-v3/include/bits/sat_arith.h b/libstdc++-v3/include/bits/sat_arith.h
new file mode 100644
index 00000000000..71793467984
--- /dev/null
+++ b/libstdc++-v3/include/bits/sat_arith.h
@@ -0,0 +1,148 @@ 
+// Saturation arithmetic -*- C++ -*-
+
+// Copyright The GNU Toolchain Authors.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file include/bits/sat_arith.h
+ *  This is an internal header file, included by other library headers.
+ *  Do not attempt to use it directly. @headername{numeric}
+ */
+
+#ifndef _GLIBCXX_SAT_ARITH_H
+#define _GLIBCXX_SAT_ARITH_H 1
+
+#pragma GCC system_header
+
+#include <bits/version.h>
+
+#ifdef __glibcxx_saturation_arithmetic // C++ >= 26
+
+#include <concepts>
+#include <ext/numeric_traits.h>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  /// Add two integers, with saturation in case of overflow.
+  template<typename _Tp> requires __is_standard_integer<_Tp>::value
+    constexpr _Tp
+    add_sat(_Tp __x, _Tp __y) noexcept
+    {
+      _Tp __z;
+      if (!__builtin_add_overflow(__x, __y, &__z))
+	return __z;
+      if constexpr (is_unsigned_v<_Tp>)
+	return __gnu_cxx::__int_traits<_Tp>::__max;
+      else if (__x < 0)
+	return __gnu_cxx::__int_traits<_Tp>::__min;
+      else
+	return __gnu_cxx::__int_traits<_Tp>::__max;
+    }
+
+  /// Subtract one integer from another, with saturation in case of overflow.
+  template<typename _Tp> requires __is_standard_integer<_Tp>::value
+    constexpr _Tp
+    sub_sat(_Tp __x, _Tp __y) noexcept
+    {
+      _Tp __z;
+      if (!__builtin_sub_overflow(__x, __y, &__z))
+	return __z;
+      if constexpr (is_unsigned_v<_Tp>)
+	return __gnu_cxx::__int_traits<_Tp>::__min;
+      else if (__x < 0)
+	return __gnu_cxx::__int_traits<_Tp>::__min;
+      else
+	return __gnu_cxx::__int_traits<_Tp>::__max;
+    }
+
+  /// Multiply two integers, with saturation in case of overflow.
+  template<typename _Tp> requires __is_standard_integer<_Tp>::value
+    constexpr _Tp
+    mul_sat(_Tp __x, _Tp __y) noexcept
+    {
+      _Tp __z;
+      if (!__builtin_mul_overflow(__x, __y, &__z))
+	return __z;
+      if constexpr (is_unsigned_v<_Tp>)
+	return __gnu_cxx::__int_traits<_Tp>::__max;
+      else if (__x < 0 != __y < 0)
+	return __gnu_cxx::__int_traits<_Tp>::__min;
+      else
+	return __gnu_cxx::__int_traits<_Tp>::__max;
+    }
+
+  /// Divide one integer by another, with saturation in case of overflow.
+  template<typename _Tp> requires __is_standard_integer<_Tp>::value
+    constexpr _Tp
+    div_sat(_Tp __x, _Tp __y) noexcept
+    {
+      __glibcxx_assert(__y != 0);
+      if constexpr (is_signed_v<_Tp>)
+	if (__x == __gnu_cxx::__int_traits<_Tp>::__min && __y == _Tp(-1))
+	  return __gnu_cxx::__int_traits<_Tp>::__max;
+      return __x / __y;
+    }
+
+  /// Divide one integer by another, with saturation in case of overflow.
+  template<typename _Res, typename _Tp>
+    requires __is_standard_integer<_Res>::value
+      && __is_standard_integer<_Tp>::value
+    constexpr _Res
+    saturate_cast(_Tp __x) noexcept
+    {
+      constexpr int __digits_R = __gnu_cxx::__int_traits<_Res>::__digits;
+      constexpr int __digits_T = __gnu_cxx::__int_traits<_Tp>::__digits;
+      constexpr _Res __max_Res = __gnu_cxx::__int_traits<_Res>::__max;
+
+      if constexpr (is_signed_v<_Res> == is_signed_v<_Tp>)
+	{
+	  if constexpr (__digits_R < __digits_T)
+	    {
+	      constexpr _Res __min_Res = __gnu_cxx::__int_traits<_Res>::__min;
+
+	      if (__x < static_cast<_Tp>(__min_Res))
+		return __min_Res;
+	      else if (__x > static_cast<_Tp>(__max_Res))
+		return __max_Res;
+	    }
+	}
+      else if constexpr (is_signed_v<_Tp>) // Res is unsigned
+	{
+	  if (__x < 0)
+	    return 0;
+	  else if (make_unsigned_t<_Tp>(__x) > __max_Res)
+	    return __gnu_cxx::__int_traits<_Res>::__max;
+	}
+      else // Tp is unsigned, Res is signed
+	{
+	  if (__x > make_unsigned_t<_Res>(__max_Res))
+	    return __max_Res;
+	}
+      return static_cast<_Res>(__x);
+    }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace
+
+#endif // __glibcxx_saturation_arithmetic
+#endif /* _GLIBCXX_SAT_ARITH_H */
diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def
index 60400b3b8d2..447fdeb9519 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1631,6 +1631,14 @@  ftms = {
   };
 };
 
+ftms = {
+  name = saturation_arithmetic;
+  values = {
+    v = 202311;
+    cxxmin = 26;
+  };
+};
+
 ftms = {
   name = to_string;
   values = {
diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h
index 2e2af3e0c41..97c6d8508f4 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -2000,6 +2000,17 @@ 
 #undef __glibcxx_want_ratio
 
 // from version.def line 1635
+#if !defined(__cpp_lib_saturation_arithmetic)
+# if (__cplusplus >  202302L)
+#  define __glibcxx_saturation_arithmetic 202311L
+#  if defined(__glibcxx_want_all) || defined(__glibcxx_want_saturation_arithmetic)
+#   define __cpp_lib_saturation_arithmetic 202311L
+#  endif
+# endif
+#endif /* !defined(__cpp_lib_saturation_arithmetic) && defined(__glibcxx_want_saturation_arithmetic) */
+#undef __glibcxx_want_saturation_arithmetic
+
+// from version.def line 1643
 #if !defined(__cpp_lib_to_string)
 # if (__cplusplus >  202302L) && _GLIBCXX_HOSTED && (__glibcxx_to_chars)
 #  define __glibcxx_to_string 202306L
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index 559e6242e92..fa8ef51c447 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -86,8 +86,13 @@ 
 #define __glibcxx_want_lcm
 #define __glibcxx_want_parallel_algorithm
 #define __glibcxx_want_ranges_iota
+#define __glibcxx_want_saturation_arithmetic
 #include <bits/version.h>
 
+#ifdef __glibcxx_saturation_arithmetic // C++ >= 26
+# include <bits/sat_arith.h>
+#endif
+
 /**
  * @defgroup numerics Numerics
  *
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/add.cc b/libstdc++-v3/testsuite/26_numerics/saturation/add.cc
new file mode 100644
index 00000000000..3eee6abca9a
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/add.cc
@@ -0,0 +1,73 @@ 
+// { dg-do compile { target c++26 } }
+
+// C++26 Saturation arithmetic [numerics.sat]
+
+#include <numeric>
+#include <limits>
+
+template<typename T, typename U>
+concept can_add_sat
+  = requires(T t, U u) { { std::add_sat(t, u) } -> std::same_as<T>; };
+
+static_assert( can_add_sat<int, int> );
+static_assert( not can_add_sat<int, short> );
+static_assert( not can_add_sat<unsigned, int> );
+static_assert( noexcept(std::add_sat(0, 0)) );
+
+using std::add_sat;
+
+// Signed type
+static_assert(add_sat(0, 0) == 0);
+static_assert(add_sat(1, 1) == 2);
+static_assert(add_sat(-1, -1) == -2);
+static_assert(add_sat(-1, 1) == 0);
+constexpr auto max = std::numeric_limits<int>::max();
+constexpr auto min = std::numeric_limits<int>::min();
+static_assert(add_sat(max, 1) == max);
+static_assert(add_sat(1, max) == max);
+static_assert(add_sat(max, max) == max);
+static_assert(add_sat(min, -1) == min);
+static_assert(add_sat(-1, min) == min);
+static_assert(add_sat(min, min) == min);
+static_assert(add_sat(max, min) == -1);
+static_assert(add_sat(min, max) == -1);
+
+// Wider signed type than the args
+static_assert(add_sat<long long>(max, max) == (long long)max * 2);
+static_assert(add_sat<long long>(min, min) == (long long)min * 2);
+
+// Signed type that undergoes integer promotion
+constexpr auto shrt_max = std::numeric_limits<short>::max();
+constexpr auto shrt_min = std::numeric_limits<short>::min();
+static_assert(add_sat<short>(0, 0) == 0);
+static_assert(add_sat<short>(1, 1) == 2);
+static_assert(add_sat<short>(shrt_max, shrt_max) == shrt_max);
+static_assert(add_sat<short>(shrt_max, 1) == shrt_max);
+static_assert(add_sat<short>(1, shrt_max) == shrt_max);
+static_assert(add_sat<short>(shrt_min, (short)-1) == shrt_min);
+static_assert(add_sat<short>((short)-1, shrt_min) == shrt_min);
+static_assert(add_sat<short>(shrt_min, (short)1) == -shrt_max);
+static_assert(add_sat<short>((short)1, shrt_min) == -shrt_max);
+
+// Unsigned type
+static_assert(add_sat(0u, 0u) == 0u);
+static_assert(add_sat(1u, 1u) == 2u);
+constexpr auto umax = std::numeric_limits<unsigned>::max();
+static_assert(add_sat(umax, 1u) == umax);
+static_assert(add_sat(1u, umax) == umax);
+static_assert(add_sat(umax, umax) == umax);
+static_assert(add_sat(0u, umax) == umax);
+static_assert(add_sat(umax, 0u) == umax);
+static_assert(add_sat(0u, 1u) == 1u);
+static_assert(add_sat(1u, 0u) == 1u);
+
+// Wider unsigned type than the args
+static_assert(add_sat<unsigned long long>(umax, umax) == (long long)umax * 2);
+
+// Unsigned type that undergoes integer promotion
+constexpr auto ushrt_max = std::numeric_limits<unsigned short>::max();
+static_assert(add_sat<unsigned short>(0, 0) == 0);
+static_assert(add_sat<unsigned short>(1, 1) == 2);
+static_assert(add_sat<unsigned short>(ushrt_max, ushrt_max) == ushrt_max);
+static_assert(add_sat<unsigned short>(ushrt_max, 1) == ushrt_max);
+static_assert(add_sat<unsigned short>(1, ushrt_max) == ushrt_max);
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/cast.cc b/libstdc++-v3/testsuite/26_numerics/saturation/cast.cc
new file mode 100644
index 00000000000..672e9c46be1
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/cast.cc
@@ -0,0 +1,24 @@ 
+// { dg-do compile { target c++26 } }
+
+// C++26 Saturation arithmetic [numerics.sat]
+
+#include <numeric>
+#include <climits>
+
+#if CHAR_BIT == 8
+static_assert(std::saturate_cast<unsigned char>(999) == 255);
+static_assert(std::saturate_cast<signed char>(999) == 127);
+#endif
+static_assert(std::saturate_cast<unsigned short>(999) == 999);
+static_assert(std::saturate_cast<signed short>(999) == 999);
+static_assert(std::saturate_cast<short>(INT_MAX) == SHRT_MAX);
+static_assert(std::saturate_cast<short>(UINT_MAX) == SHRT_MAX);
+static_assert(std::saturate_cast<short>(UINT_MAX) == SHRT_MAX);
+static_assert(std::saturate_cast<unsigned short>(UINT_MAX) == USHRT_MAX);
+static_assert(std::saturate_cast<int>(UINT_MAX) == INT_MAX);
+static_assert(std::saturate_cast<int>(INT_MAX) == INT_MAX);
+static_assert(std::saturate_cast<unsigned>(-1) == 0);
+static_assert(std::saturate_cast<unsigned>(INT_MIN) == 0);
+static_assert(std::saturate_cast<unsigned>(UINT_MAX) == UINT_MAX);
+static_assert(std::saturate_cast<unsigned>(LLONG_MAX) == UINT_MAX);
+static_assert(std::saturate_cast<unsigned>(ULLONG_MAX) == UINT_MAX);
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/div.cc b/libstdc++-v3/testsuite/26_numerics/saturation/div.cc
new file mode 100644
index 00000000000..a3f43573651
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/div.cc
@@ -0,0 +1,45 @@ 
+// { dg-do compile { target c++26 } }
+
+// C++26 Saturation arithmetic [numerics.sat]
+
+#include <numeric>
+#include <climits>
+
+template<typename T, typename U>
+concept can_div_sat
+  = requires(T t, U u) { { std::div_sat(t, u) } -> std::same_as<T>; };
+
+static_assert( can_div_sat<int, int> );
+static_assert( not can_div_sat<int, short> );
+static_assert( not can_div_sat<unsigned, int> );
+static_assert( noexcept(std::div_sat(0, 1)) );
+
+using std::div_sat;
+
+static_assert(std::div_sat(0, 1) == 0);
+static_assert(std::div_sat(0, -1) == 0);
+static_assert(std::div_sat(1, -1) == -1);
+static_assert(std::div_sat(10, -2) == -5);
+static_assert(std::div_sat(-10, -2) == 5);
+static_assert(std::div_sat(INT_MAX, 1) == INT_MAX);
+static_assert(std::div_sat(INT_MIN, 1) == INT_MIN);
+static_assert(std::div_sat(INT_MIN + 1, -1) == INT_MAX);
+static_assert(std::div_sat(0u, 1u) == 0u);
+static_assert(std::div_sat(UINT_MAX, 1u) == UINT_MAX);
+static_assert(std::div_sat(INT_MIN, -1) == INT_MAX);
+static_assert(std::div_sat((short)SHRT_MIN, (short)-1) == SHRT_MAX);
+static_assert(std::div_sat(LONG_MIN, -1L) == LONG_MAX);
+static_assert(std::div_sat(LLONG_MIN, -1LL) == LLONG_MAX);
+
+template<auto N>
+std::integral_constant<decltype(N), std::div_sat(N, N-N)>
+div_sat_by_zero();
+
+template<auto N>
+concept can_div_sat_by_zero = requires { div_sat_by_zero<N>(); };
+
+static_assert( not can_div_sat_by_zero<0> );
+static_assert( not can_div_sat_by_zero<1> );
+static_assert( not can_div_sat_by_zero<1u> );
+static_assert( not can_div_sat_by_zero<-1L> );
+static_assert( not can_div_sat_by_zero<short(99)> );
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/mul.cc b/libstdc++-v3/testsuite/26_numerics/saturation/mul.cc
new file mode 100644
index 00000000000..1b5538c9af3
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/mul.cc
@@ -0,0 +1,34 @@ 
+// { dg-do compile { target c++26 } }
+
+// C++26 Saturation arithmetic [numerics.sat]
+
+#include <numeric>
+#include <climits>
+
+template<typename T, typename U>
+concept can_mul_sat
+  = requires(T t, U u) { { std::mul_sat(t, u) } -> std::same_as<T>; };
+
+static_assert( can_mul_sat<int, int> );
+static_assert( not can_mul_sat<int, short> );
+static_assert( not can_mul_sat<unsigned, int> );
+static_assert( noexcept(std::mul_sat(0, 0)) );
+
+using std::mul_sat;
+
+static_assert(mul_sat(1, 1) == 1);
+static_assert(mul_sat(10, 11) == 110);
+static_assert(mul_sat(INT_MAX / 2, 3) == INT_MAX);
+static_assert(mul_sat(INT_MAX / 2, -3) == INT_MIN);
+static_assert(mul_sat(INT_MAX / -2, 3) == INT_MIN);
+static_assert(mul_sat(INT_MIN / 2, -3) == INT_MAX);
+static_assert(mul_sat(INT_MIN, -1) == INT_MAX);
+static_assert(mul_sat(INT_MAX, -1) == INT_MIN + 1);
+static_assert(mul_sat(INT_MAX, INT_MAX) == INT_MAX);
+static_assert(mul_sat(INT_MAX, -INT_MAX) == INT_MIN);
+static_assert(mul_sat(UINT_MAX, UINT_MAX) == UINT_MAX);
+static_assert(mul_sat(UINT_MAX, 0u) == 0);
+static_assert(mul_sat(0u, UINT_MAX) == 0);
+static_assert(mul_sat((short)SHRT_MAX, (short)2) == SHRT_MAX);
+static_assert(mul_sat((short)SHRT_MAX, (short)SHRT_MIN) == SHRT_MIN);
+static_assert(mul_sat<long long>(SHRT_MAX, 2) == 2L * SHRT_MAX);
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/sub.cc b/libstdc++-v3/testsuite/26_numerics/saturation/sub.cc
new file mode 100644
index 00000000000..c56154a49ff
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/sub.cc
@@ -0,0 +1,86 @@ 
+// { dg-do compile { target c++26 } }
+
+// C++26 Saturation arithmetic [numerics.sat]
+
+#include <numeric>
+#include <limits>
+
+template<typename T, typename U>
+concept can_sub_sat
+  = requires(T t, U u) { { std::sub_sat(t, u) } -> std::same_as<T>; };
+
+static_assert( can_sub_sat<int, int> );
+static_assert( not can_sub_sat<int, short> );
+static_assert( not can_sub_sat<unsigned, int> );
+static_assert( noexcept(std::sub_sat(0, 0)) );
+
+using std::sub_sat;
+
+// Signed type
+static_assert(sub_sat(0, 0) == 0);
+static_assert(sub_sat(1, 1) == 0);
+static_assert(sub_sat(-1, -1) == 0);
+static_assert(sub_sat(-1, 1) == -2);
+constexpr auto max = std::numeric_limits<int>::max();
+constexpr auto min = std::numeric_limits<int>::min();
+static_assert(sub_sat(max, 1) == max - 1);
+static_assert(sub_sat(1, max) == 1 - max);
+static_assert(sub_sat(max, max) == 0);
+static_assert(sub_sat(min, 1) == min);
+static_assert(sub_sat(min, 123) == min);
+static_assert(sub_sat(0, max) == min + 1);
+static_assert(sub_sat(-1, max) == min);
+static_assert(sub_sat(-2, max) == min);
+static_assert(sub_sat(-2, min) == max - 1);
+static_assert(sub_sat(-1, min) == max);
+static_assert(sub_sat(0, min) == max);
+static_assert(sub_sat(1, min) == max);
+static_assert(sub_sat(min, -1) == min + 1);
+static_assert(sub_sat(min, min) == 0);
+static_assert(sub_sat(max, min) == max);
+static_assert(sub_sat(min, max) == min);
+
+// Wider signed type than the args
+static_assert(sub_sat<long long>(max, min) == (long long)max * 2 + 1);
+static_assert(sub_sat<long long>(min, max) == (long long)min * 2 + 1);
+
+// Signed type that undergoes integer promotion
+constexpr auto shrt_max = std::numeric_limits<short>::max();
+constexpr auto shrt_min = std::numeric_limits<short>::min();
+static_assert(sub_sat<short>(0, 0) == 0);
+static_assert(sub_sat<short>(1, 1) == 0);
+static_assert(sub_sat<short>(3, 1) == 2);
+static_assert(sub_sat<short>(shrt_max, shrt_max) == 0);
+static_assert(sub_sat<short>(shrt_max, 1) == shrt_max - 1);
+static_assert(sub_sat<short>(1, shrt_max) == shrt_min + 2);
+static_assert(sub_sat<short>(shrt_max, shrt_min) == shrt_max);
+static_assert(sub_sat<short>(0, shrt_min) == shrt_max);
+static_assert(sub_sat<short>(shrt_min, (short)1) == shrt_min);
+static_assert(sub_sat<short>(shrt_min, (short)-1) == shrt_min + 1);
+static_assert(sub_sat<short>((short)-1, shrt_min) == shrt_max);
+static_assert(sub_sat<short>((short)1, shrt_min) == shrt_max);
+
+// Unsigned type
+static_assert(sub_sat(0u, 0u) == 0u);
+static_assert(sub_sat(1u, 1u) == 0u);
+static_assert(sub_sat(-1u, -1u) == 0u);
+static_assert(sub_sat(-1u, 1u) == -2u);
+constexpr auto umax = std::numeric_limits<unsigned>::max();
+static_assert(sub_sat(0u, 1u) == 0u);
+static_assert(sub_sat(umax, umax) == 0u);
+static_assert(sub_sat(umax, 0u) == umax);
+static_assert(sub_sat(0u, umax) == 0u);
+static_assert(sub_sat(umax, 1u) == umax - 1u);
+static_assert(sub_sat(0u, 0u) == 0u);
+
+// Wider unsigned type than the args
+static_assert(sub_sat<unsigned long long>(0u, umax) == 0u);
+
+// Unsigned type that undergoes integer promotion
+constexpr auto ushrt_max = std::numeric_limits<unsigned short>::max();
+static_assert(sub_sat<unsigned short>(0, 0) == 0);
+static_assert(sub_sat<unsigned short>(1, 1) == 0);
+static_assert(sub_sat<unsigned short>(3, 1) == 2);
+static_assert(sub_sat<unsigned short>(ushrt_max, ushrt_max) == 0);
+static_assert(sub_sat<unsigned short>(0, 1) == 0);
+static_assert(sub_sat<unsigned short>(1, ushrt_max) == 0);
diff --git a/libstdc++-v3/testsuite/26_numerics/saturation/version.cc b/libstdc++-v3/testsuite/26_numerics/saturation/version.cc
new file mode 100644
index 00000000000..ca94ef1212a
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/saturation/version.cc
@@ -0,0 +1,19 @@ 
+// { dg-do preprocess { target c++26 } }
+// { dg-add-options no_pch }
+
+#include <numeric>
+
+#ifndef __cpp_lib_saturation_arithmetic
+# error "Feature test macro for saturation arithmetic is missing in <numeric>"
+#elif __cpp_lib_saturation_arithmetic < 202311L
+# error "Feature test macro for saturation arithmetic has wrong value in <numeric>"
+#endif
+
+#undef __cpp_lib_saturation_arithmetic
+#include <version>
+
+#ifndef __cpp_lib_saturation_arithmetic
+# error "Feature test macro for saturation arithmetic is missing in <version>"
+#elif __cpp_lib_saturation_arithmetic < 202311L
+# error "Feature test macro for saturation arithmetic has wrong value in <version>"
+#endif