[PATCH] libstc++: Improve list assumption after constructor [PR118865]

[Jonathan Wakely]

On Fri, 14 Feb 2025, 18:34 Andrew Pinski (QUIC), <quic_apinski@quicinc.com>
wrote:

> > -----Original Message-----
> > From: Jonathan Wakely <jwakely@redhat.com>
> > Sent: Friday, February 14, 2025 6:49 AM
> > To: Andrew Pinski (QUIC) <quic_apinski@quicinc.com>
> > Cc: gcc-patches@gcc.gnu.org; libstdc++@gcc.gnu.org
> > Subject: Re: [PATCH] libstc++: Improve list assumption after
> > constructor [PR118865]
> >
> > On Fri, 14 Feb 2025 at 03:03, Andrew Pinski
> > <quic_apinski@quicinc.com> wrote:
> > >
> > > The code example here does:
> > > ```
> > > if (begin == end) __builtin_unreachable(); std::list nl(begin,
> > end);
> > >
> > > for (auto it = nl.begin(); it != nl.end(); it++) { ...
> > > }
> > > /* Remove the first element of the list. */
> > nl.erase(nl.begin()); ```
> > >
> > > And we get a warning because because we jump threaded
> > the case were we
> > > think the list was empty from the for loop BUT we populated
> > it without
> > > an empty array. So can help the compiler here by adding that
> > after
> > > initializing the list with non empty array, that the list will not
> > be empty either.
> > >
> > > This is able to remove the -Wfree-nonheap-object warning in
> > the first
> > > reduced testcase (with the fix for `begin == end` case added)
> > in the
> > > PR 118865; the second reduced testcase has been filed off as
> > PR 118867.
> > >
> > > Bootstrapped and tested on x86_64-linux-gnu.
> > >
> > > libstdc++-v3/ChangeLog:
> > >
> > >         PR libstdc++/118865
> > >         * include/bits/stl_list.h (_M_initialize_dispatch): Add an
> > >         unreachable if the iterator was not empty that the list
> > will
> > >         now be not empty.
> > >
> > > Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
> > > ---
> > >  libstdc++-v3/include/bits/stl_list.h | 6 ++++++
> > >  1 file changed, 6 insertions(+)
> > >
> > > diff --git a/libstdc++-v3/include/bits/stl_list.h
> > > b/libstdc++-v3/include/bits/stl_list.h
> > > index be33eeb03d4..f987d8b9d0a 100644
> > > --- a/libstdc++-v3/include/bits/stl_list.h
> > > +++ b/libstdc++-v3/include/bits/stl_list.h
> > > @@ -2384,12 +2384,18 @@
> > _GLIBCXX_BEGIN_NAMESPACE_CXX11
> > >         _M_initialize_dispatch(_InputIterator __first,
> > _InputIterator __last,
> > >                                __false_type)
> > >         {
> > > +         bool __notempty = __first != __last;
> > >           for (; __first != __last; ++__first)  #if __cplusplus >=
> > > 201103L
> > >             emplace_back(*__first);
> > >  #else
> > >             push_back(*__first);
> > >  #endif
> > > +        if (__notempty)
> > > +          {
> > > +            if (begin() == end())
> > > +              __builtin_unreachable();
> > > +          }
> >
> > Would there be any benefit in also telling the compiler that
> > when first==last that the resulting list *is* empty?
>
> I was debating if that would be useful but then I looked and noticed the
> compiler could already figure it. The reason is begin for a list is a
> wrapper around an addition of a pointer and a constant. Pre is able to
> optimize the case which then will be used to jump thread later on.
> Also I think a too complex leading to the unreachable will not help the
> compiler out at all.
>
> An example is:
> ```
>
> int *g(int);
>
> int f(int **a, int b, int c, int *d)
> {
>   *a = d;
>   for(int i = 0; i < c; i++)
>     *a = g(i);
> #ifdef ADD_UNREACHABLE
>   if (c >= 0)
>     if (*a == d)
>       __builtin_unreachable();
> #endif
>   if (*a == d)
>     return 1;
>   return 0;
> }
> ```
> GCC is able to optimize away the last condition for the case of `(c <= 0)`
> and when defining ADD_UNREACHABLE can now optimize away the condition fully.
>
> >
> > so e.g.
> >
> >   const bool __empty = __first == __last;
> >   // loop
> >   if (__empty != (begin() == end()))
> >     __builtin_unreachable();
> >
> >
> > Testing first == last twice for the first iteration bugs me a little,
> > but I assume that can be optimized? Or should we use a do-
> > while?
>
> Yes does get optimized away. See above. For the typical iterator the
> comparison, will be max 2 loads followed by a comparison of that (or no
> loads) and GCC's early passes does a nice job at optimizing that.


The patch is OK for trunk then, thanks.



>
> Thanks,
> Andrew Pinski
>
> >
> >           if (__first != __last)
> >             {
> >               do
> >                 {
> > #if __cplusplus >= 201103L
> >                   emplace_back(*__first); #else
> >                   push_back(*__first);
> > #endif
> >                 } while (++__first != __last);
> >               if (begin() == end())
> >                 __builtin_unreachable();
> >             }
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250214/7111b8c6/attachment.htm>