> -----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.
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();
> }
