On Fri, 17 Nov 2023 at 17:01, Daniel Krügler <daniel.krueg...@gmail.com> wrote:
>
> Am Fr., 17. Nov. 2023 um 16:32 Uhr schrieb Jonathan Wakely
> <jwak...@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).
