On Fri, 14 Feb 2025, 18:34 Andrew Pinski (QUIC), <quic_apin...@quicinc.com>
wrote:
> > -----Original Message-----
> > From: Jonathan Wakely <jwak...@redhat.com>
> > Sent: Friday, February 14, 2025 6:49 AM
> > To: Andrew Pinski (QUIC) <quic_apin...@quicinc.com>
> > Cc: gcc-patches@gcc.gnu.org; libstd...@gcc.gnu.org
> > Subject: Re: [PATCH] libstc++: Improve list assumption after
> > constructor [PR118865]
> >
> > On Fri, 14 Feb 2025 at 03:03, Andrew Pinski
> > <quic_apin...@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_apin...@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();
> > }
>
>
