[Bug c++/105838] New: g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[Bug c++/105838] New: g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[eisjmbjdfcukqlaely at nthrl dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

            Bug ID: 105838
           Summary: g++ 12.1.0 runs out of memory or time when building
                    const std::vector of std::strings
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: eisjmbjdfcukqlaely at nthrl dot com
  Target Milestone: ---

Created attachment 53078
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53078&action=edit
Output of  "g++ -E tmp_in.cpp > tmp_in.ii"

While porting a Wordle-like game from an interpreted language to C++
(ironically, in an attempt at getting better performance from a compiled
language!) it was found that g++ 12.1.0 cannot even initialize a const
std::vector of known fixed-length words.

Here is g++ 12.1.0 running out of memory (16GB RAM + 8GB swap) with -O1, after
about a minute:
```
$ g++ tmp_in.cpp -O1
g++: fatal error: Killed signal terminated program cc1plus
compilation terminated.
```

If optimization is disabled in an attempt to save memory, g++ takes
unreasonably long and gets killed after 300 seconds:
```
$ timeout 300 g++ tmp_in.cpp   # gets killed after 300 seconds with no a.out
```

Output of g++ -v:
```
$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure
--enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-bootstrap
--prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/
--with-linker-hash-style=gnu --with-system-zlib --enable-__cxa_atexit
--enable-cet=auto --enable-checking=release --enable-clocale=gnu
--enable-default-pie --enable-default-ssp --enable-gnu-indirect-function
--enable-gnu-unique-object --enable-linker-build-id --enable-lto
--enable-multilib --enable-plugin --enable-shared --enable-threads=posix
--disable-libssp --disable-libstdcxx-pch --disable-werror
--with-build-config=bootstrap-lto --enable-link-serialization=1
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 12.1.0 (GCC) 
```

For comparison, here is clang++ 13.0.1 building in about 5 seconds without
optimization:
```
$ /usr/bin/time --verbose clang++ tmp_in.cpp 
tmp_in.cpp:1797:19: warning: format specifies type 'int' but the argument has
type 'std::vector::size_type' (aka 'unsigned long') [-Wformat]
  printf ("%d\n", lst.size());
           ~~     ^~~~~~~~~~
           %zu
1 warning generated.
        Command being timed: "clang++ tmp_in.cpp"
        User time (seconds): 4.69
        System time (seconds): 0.17

$ ./a.out
21437
```

If optimization is enabled with -O1, clang++ 13.0.1 still successfully compiles
it, though it takes just over 2 minutes and almost 4GB RAM:
```
$ /usr/bin/time --verbose clang++ tmp_in.cpp -O1
tmp_in.cpp:1797:19: warning: format specifies type 'int' but the argument has
type 'std::vector::size_type' (aka 'unsigned long') [-Wformat]
  printf ("%d\n", lst.size());
           ~~     ^~~~~~~~~~
           %zu
1 warning generated.
        Command being timed: "clang++ tmp_in.cpp -O1"
        User time (seconds): 125.31
        System time (seconds): 0.81
        Maximum resident set size (kbytes): 3675076

$ ./a.out
21437
```

Output of clang++ -v for completeness:
```
 clang++ -v
clang version 13.0.1
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin
Found candidate GCC installation:
/usr/bin/../lib/gcc/x86_64-pc-linux-gnu/12.1.0
Found candidate GCC installation:
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/12.1.0
Selected GCC installation: /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/12.1.0
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Selected multilib: .;@m64
```

[Bug c++/105838] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-06-13

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed with -O1.  At -O0 I see

> /usr/bin/time /space/rguenther/install/gcc-12.1/bin/g++ -S t.C
13.44user 0.34system 0:15.71elapsed 87%CPU (0avgtext+0avgdata
1139560maxresident)k
65584inputs+23864outputs (77major+275588minor)pagefaults 0swaps

with -O1 it uses >20GB of memory in cleanup_all_empty_eh.  It might be
the order of optimizing this is exposing some quadratic amount of
edge redirection, I have not yet analyzed this in detail but trimming down
the testcase should help here.  There isn't much allocation done here
besides the edge redirection SSA update stuff for PHIs.

[Bug c++/105838] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.3.0

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 is also an order of magnitude slower.

[Bug c++/105838] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 53133
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53133&action=edit
unincluded, and reduced

This "reduced" testcase peaks at 3.8GB memory.

> /usr/bin/time /space/rguenther/install/gcc-12.1/bin/g++ -S -O /tmp/t.C
8.68user 1.13system 0:10.03elapsed 97%CPU (0avgtext+0avgdata
3813480maxresident)k
17328inputs+2104outputs (28major+961476minor)pagefaults 0swaps

simply doubling the initializer grows it to 14.8GB

> /usr/bin/time /space/rguenther/install/gcc-12.1/bin/g++ -S -O /tmp/t.C
43.02user 4.49system 0:47.51elapsed 99%CPU (0avgtext+0avgdata
14861052maxresident)k
0inputs+4088outputs (0major+3727738minor)pagefaults 0swaps

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|g++ 12.1.0 runs out of      |[10/11/12/13 Regression]
                   |memory or time when         |g++ 12.1.0 runs out of
                   |building const std::vector  |memory or time when
                   |of std::strings             |building const std::vector
                   |                            |of std::strings
             Blocks|                            |93199
   Target Milestone|---                         |10.4
           Priority|P3                          |P2
                 CC|                            |ebotcazou at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Memory usage is from cleanup_empty_eh_merge_phis which deals with a very large
number of incoming edges, recording the edge/var mappings.  This likely runs
into

  /* The post-order traversal may lead to quadraticness in the redirection
     of incoming EH edges from inner LPs, so first try to walk the region
     tree from inner to outer LPs in order to eliminate these edges.  */

where we end up re-directing more and more edges again and again.  Still the
peak memory use is odd, but it might be simply GC garbage piling up in the
CFG manipulation odyssee.

It's removal of MNT regions - with just 3 elements we go in ehcleanup1 from

Before removal of unreachable regions:
Eh tree:
   25 must_not_throw
   1 cleanup land:{12,<L26>}
     24 cleanup
     23 must_not_throw
     2 cleanup land:{11,<L25>}
       22 must_not_throw
       3 cleanup land:{10,<L18>}
         21 must_not_throw
         4 cleanup land:{9,<L17>}
           20 must_not_throw
           5 cleanup land:{1,<L16>}
             19 must_not_throw
             6 cleanup land:{8,<L15>}
               18 must_not_throw
               7 cleanup land:{2,<L14>}
                 17 must_not_throw
                 8 cleanup land:{7,<L13>}
                   16 must_not_throw
                   9 cleanup land:{3,<L12>}
                     15 must_not_throw
                     10 cleanup land:{6,<L8>}
                       14 must_not_throw
                       11 cleanup land:{5,<L7>}
                         13 must_not_throw
                         12 cleanup land:{4,<L6>}

to

After removal of unreachable regions:
Eh tree:
   1 cleanup land:{12,<L26>}
     2 cleanup land:{11,<L25>}
       3 cleanup land:{10,<L18>}
         4 cleanup land:{9,<L17>}
           5 cleanup land:{1,<L16>}
             6 cleanup land:{8,<L15>}
               7 cleanup land:{2,<L14>}
                 8 cleanup land:{7,<L13>}
                   9 cleanup land:{3,<L12>}
                     10 cleanup land:{6,<L8>}
                       11 cleanup land:{5,<L7>}
                         12 cleanup land:{4,<L6>}

but we do this in a sub-optimal order.  Axing the first walk:

  for (i = vec_safe_length (cfun->eh->lp_array) - 1; i >= 1; --i)
    {
      lp = (*cfun->eh->lp_array)[i];
      if (lp)
        changed |= cleanup_empty_eh (lp);
    }

fixes this but it will go against the PR93199 fix in r10-5868-g5eaf0c498f718f,
which the followup r11-3234-gaab6194d0898f5 preserved.  I fear the
optimal order is different for the clobber optimizations and the edge
redirection overhead.

In any case a fix should be evaluated against the PR93199 testcase as well.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93199
[Bug 93199] [9 Regression] Compile time hog in sink_clobbers

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
btw, the unincluded testcase ended up too small, not matching the posted
numbers (I had to hit reload and cut it further at that point ...).

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jason at gcc dot gnu.org,
                   |                            |redi at gcc dot gnu.org

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Note, for say
#include <string>
#include <vector>

void foo (const std::vector<std::string> &);
int main ()
{
  const std::vector<std::string> lst = {
  "aahing", "aaliis", "aarrgh", "abacas", "abacus", "abakas", "abamps",
"abands", "abased", "abaser", "abases", "abasia" };
  foo (lst);
}
one gets terrible code from both g++ and clang++, in both cases it is serial
code calling many std::string ctors with the string literal arguments
that perhaps later on are inlined.  Over 21000 times in a row.  That also means
over 21000 memory allocations etc.
For your game, the obvious first question would be if you really need
std::vector of std::string in this case and if a normal array of const char *
strings wouldn't be better, that can be initialized at compile time.
Or, if you really need std::vector<std::string>, if it wouldn't be better to
use array of const char * and build the
vector from it (sizeof (arr) / sizeof (arr[0]) to reserve that many elts in the
vector, then a loop that will construct
the std::string objects and move them into the list).

On the compiler side, a question is if we shouldn't detect such kind of
initializers and if they have over some param determined number of elements
which have the same type / kind (or at least a large sequence of such), don't
emit those
                    std::allocator<char>::allocator (&D.37541);
                    try
                      {
                        std::__cxx11::basic_string<char>::basic_string<> (_4,
"aahing", &D.37541);
                        D.37581 = D.37581 + 32;
                        D.37582 = D.37582 + -1;
                        _5 = D.37581;
                        try
                          {
                            std::allocator<char>::allocator (&D.37543);
                            try
                              {
                               
std::__cxx11::basic_string<char>::basic_string<> (_5, "aaliis", &D.37543);
                                D.37581 = D.37581 + 32;
                                D.37582 = D.37582 + -1;
                                _6 = D.37581;
                                try
                                  {
...
but a loop.  Doesn't have to be just for the STL types, if we have
struct S { S (int); ... };
  const S s[] = { 1, 3, 22, 42, 132, -12, 18, 19, 32, 0, 25, ... };
then again there should be some upper limit over which we'd just emit:
  const S s[count];
  static const int stemp[count] = { 1, 3, 22, 42, 132, -12, 18, 19, 32, 0, 25,
... };
  for (size_t x = 0; x < count; ++x) S (&s[x], stemp[x]);
or so (of course, with destruction possibility if some ctor may throw).

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |robert.durkacz at gmail dot com

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 106241 has been marked as a duplicate of this bug. ***

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[luydorarko at vusra dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

luydorarko at vusra dot com <luydorarko at vusra dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |luydorarko at vusra dot com

--- Comment #9 from luydorarko at vusra dot com <luydorarko at vusra dot com> ---
Comment re Bug #106241 being marked as a duplicate of this bug #105838. This
bug #105838 is marked as affecting only gcc versions 10/11/12/13 and is
triggered only on -O1 or higher optimization due to quadratic behavior seen
with "only" 21K strings. Bug #106241 refers to gcc 7.5.0 and is triggered even
without -O1 but needs millions (!!) of strings to do so. Acknowledging that
both result in OOM, they do not resemble each other beyond that.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Jason Merrill <jason at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #10 from Jason Merrill <jason at gcc dot gnu.org> ---
A lot of the problem here is that building a std::string involves building a
std::allocator<char> temporary to pass to the string constructor, and then we
need to wait until the entire array is built before we can destroy any of them:
https://eel.is/c++draft/class.temporary#5 says we can only destroy temporaries
early if there was no initializer for that array element.  So for each element
of the initializer we have another EH region for its allocator temporary.

We could do better for the general case by creating a parallel array of
temporaries and using the same single cleanup region for it as for the array of
strings.  This seems like a worthwhile general optimization.

We might be able to do better for the specific case by recognizing that
std::allocator has no data and nothing cares about its address, so we can go
ahead and destroy it after initializing the string, and reuse the stack slot. 
This also saves stack space.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Jason Merrill from comment #10)
> A lot of the problem here is that building a std::string involves building a
> std::allocator<char> temporary to pass to the string constructor, and then
> we need to wait until the entire array is built before we can destroy any of
> them: https://eel.is/c++draft/class.temporary#5 says we can only destroy
> temporaries early if there was no initializer for that array element.  So
> for each element of the initializer we have another EH region for its
> allocator temporary.
> 
> We could do better for the general case by creating a parallel array of
> temporaries and using the same single cleanup region for it as for the array
> of strings.  This seems like a worthwhile general optimization.
> 
> We might be able to do better for the specific case by recognizing that
> std::allocator has no data and nothing cares about its address, so we can go
> ahead and destroy it after initializing the string, and reuse the stack
> slot.  This also saves stack space.

Even if we don't emit a loop (which I still think is the way to go for larger
initializers because anything else means just too large code), can't there for
the larger initializers simply be some variable holding a counter how many
initializers have been already initialized and a single EH region that will
perform all the cleanups based on that counter?

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #12 from Jason Merrill <jason at gcc dot gnu.org> ---
Another significant part of the problem is that vector<string> doesn't have a
generic initializer_list constructor.  Adding

      template <typename __elt>
      _GLIBCXX20_CONSTEXPR
      vector(initializer_list<__elt> __l,
             const allocator_type& __a = allocator_type())
      : _Base(__a)
      {
        _M_range_initialize(__l.begin(), __l.end(),
                            random_access_iterator_tag());
      }

so that it can construct from initializer_list<const char *> makes the
construction into a simple loop over a static array.

Users can do this optimization manually by writing e.g.

  auto init = {
  "aahing", "aaliis", "aarrgh", "abacas", "abacus", "abakas", "abamps",
"abands", "abased", "abaser", "abases", "abasia",
  };
  const std::vector<std::string> lst (init.begin(), init.end());

and so using the (template) iterator constructor instead of the (non-template)
initializer_list constructor.  But that shouldn't be necessary.

Jonathan, has anyone suggested adding generic init_list constructors to the
container classes?

What do you think about doing the above translation in the compiler?  Is the
compiler allowed to do that?

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #13 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #11)
> Even if we don't emit a loop (which I still think is the way to go for
> larger initializers because anything else means just too large code), can't
> there for the larger initializers simply be some variable holding a counter
> how many initializers have been already initialized and a single EH region
> that will perform all the cleanups based on that counter?

We already do that for cleaning up the array itself; the problem is any
temporaries created while initializing array elements.  That's why I was
thinking about a parallel array of temporaries.  Though that would only work if
all the element initializers construct the same temporaries, which is true in
this case but not in general.

But really I think we should try to avoid constructing an array of std::string
in the first place, as in comment #12.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jason Merrill from comment #12)
> Another significant part of the problem is that vector<string> doesn't have
> a generic initializer_list constructor.  Adding
> 
>       template <typename __elt>
>       _GLIBCXX20_CONSTEXPR
>       vector(initializer_list<__elt> __l,
>              const allocator_type& __a = allocator_type())
>       : _Base(__a)
>       {
>         _M_range_initialize(__l.begin(), __l.end(),
>                             random_access_iterator_tag());
>       }
> 
> so that it can construct from initializer_list<const char *> makes the
> construction into a simple loop over a static array.

Which is potentially *much* more efficient, because it constructs the strings
in place, instead of making unelidable copies of the initializer_list elements.

> Jonathan, has anyone suggested adding generic init_list constructors to the
> container classes?

Not that I'm aware of. There might be concerns about introducing more
ambiguities like the vector<int>{1,2} case.

> What do you think about doing the above translation in the compiler?  Is the
> compiler allowed to do that?

Good question.

If the compiler first checked that the code as-written would call the
initializer_list<value_type> constructor (and not some other constructor) then
it should be safe to do it.

In the general case, somebody would probably find a way to notice and complain.
But if you're thinking of optimizing the specific case of vector<string> then I
think it would be unobservable. The string copies can't be observed, because
it's unspecified when and how often std::allocator calls operator new.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So, do we want a new attribute on allocator to tell the compiler that it is a
class whose methods don't care about the address of the object and it has
trivial ctor and dtor and it is enough to construct it once instead of many
times, or shall the C++ FE hardcode it for std::allocator template if it sees
certain things in the header?
Not constructing thousands of these would be nice.
The temporary arrays might be a good idea for the more general case if we can't
optimize it better.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[jason at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #16 from Jason Merrill <jason at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #14)
> > Jonathan, has anyone suggested adding generic init_list constructors to the
> > container classes?
> 
> Not that I'm aware of. There might be concerns about introducing more
> ambiguities like the vector<int>{1,2} case.

Yes, I had to constrain it to when there is a conversion from __elt to
value_type.  Might as well also require value_type to be a class.

> > What do you think about doing the above translation in the compiler?  Is the
> > compiler allowed to do that?
> 
> Good question.
> 
> If the compiler first checked that the code as-written would call the
> initializer_list<value_type> constructor (and not some other constructor)
> then it should be safe to do it.

My current hack checks for a list of at least 8 elements to exclude other
constructors, but checking actual overload resolution does sound safer.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #17 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:1e1847612d7f169f82c985b0b3a5e3301d6fe999

commit r13-4563-g1e1847612d7f169f82c985b0b3a5e3301d6fe999
Author: Jason Merrill <jason@redhat.com>
Date:   Mon Dec 5 15:19:27 2022 -0500

    c++: fewer allocator temps [PR105838]

    In this PR, initializing the array of std::string to pass to the vector
    initializer_list constructor gets very confusing to the optimizers as the
    number of elements increases, primarily because of all the std::allocator
    temporaries passed to all the string constructors.  Instead of creating one
    for each string, let's share an allocator between all the strings; we can
do
    this safely because we know that std::allocator is stateless and that
string
    doesn't care about the object identity of its allocator parameter.

            PR c++/105838

    gcc/cp/ChangeLog:

            * cp-tree.h (is_std_allocator): Declare.
            * constexpr.cc (is_std_allocator): Split out  from...
            (is_std_allocator_allocate): ...here.
            * init.cc (find_temps_r): New.
            (find_allocator_temp): New.
            (build_vec_init): Use it.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/allocator-opt1.C: New test.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #18 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:d081807d8d70e3e87eae41e1560e54d503f4d465

commit r13-4564-gd081807d8d70e3e87eae41e1560e54d503f4d465
Author: Jason Merrill <jason@redhat.com>
Date:   Tue Dec 6 09:51:51 2022 -0500

    c++: avoid initializer_list<string> [PR105838]

    When constructing a vector<string> from { "strings" }, first is built an
    initializer_list<string>, which is then copied into the strings in the
    vector.  But this is inefficient: better would be treat the { "strings" }
    as a range and construct the strings in the vector directly from the
    string-literals.  We can do this transformation for standard library
    classes because we know the design patterns they follow.

            PR c++/105838

    gcc/cp/ChangeLog:

            * call.cc (list_ctor_element_type): New.
            (braced_init_element_type): New.
            (has_non_trivial_temporaries): New.
            (maybe_init_list_as_array): New.
            (maybe_init_list_as_range): New.
            (build_user_type_conversion_1): Use maybe_init_list_as_range.
            * parser.cc (cp_parser_braced_list): Call
            recompute_constructor_flags.
            * cp-tree.h (find_temps_r): Declare.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/initlist-opt1.C: New test.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #19 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:bd0485f20f4794f9787237706a6308473a8e9415

commit r13-4565-gbd0485f20f4794f9787237706a6308473a8e9415
Author: Jason Merrill <jason@redhat.com>
Date:   Tue Dec 6 18:10:48 2022 -0500

    c++: build initializer_list<string> in a loop [PR105838]

    The previous patch avoided building an initializer_list<string> at all when
    building a vector<string>, but in situations where that isn't possible, we
    could still build the initializer_list with a loop over a constant array.

    This is represented using a VEC_INIT_EXPR, which required adjusting a
couple
    of places that expected the initializer array to have the same type as the
    target array and fixing build_vec_init not to undo our efforts.

            PR c++/105838

    gcc/cp/ChangeLog:

            * call.cc (convert_like_internal) [ck_list]: Use
            maybe_init_list_as_array.
            * constexpr.cc (cxx_eval_vec_init_1): Init might have
            a different type.
            * tree.cc (build_vec_init_elt): Likewise.
            * init.cc (build_vec_init): Handle from_array from a
            TARGET_EXPR.  Retain TARGET_EXPR of a different type.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/initlist-opt2.C: New test.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #20 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:4ef521bbc63f8a3883d507a8b6c1f95f442df3fe

commit r13-4712-g4ef521bbc63f8a3883d507a8b6c1f95f442df3fe
Author: Jason Merrill <jason@redhat.com>
Date:   Wed Dec 14 17:42:52 2022 -0500

    c++: fix initializer_list transformation [PR108071]

    In these testcases, we weren't adequately verifying that constructing the
    element type from an array element would have the same effect as
    constructing it from one of the initializers.

            PR c++/108071
            PR c++/105838

    gcc/cp/ChangeLog:

            * call.cc (struct conversion_obstack_sentinel): New.
            (maybe_init_list_as_array): Compare conversion of dummy argument.

    gcc/testsuite/ChangeLog:

            * g++.dg/cpp0x/initlist131.C: New test.
            * g++.dg/cpp0x/initlist132.C: New test.
            * g++.dg/cpp0x/initlist133.C: New test.

[Bug c++/105838] [10/11/12/13 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #21 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:01ea66a6c56e53163d9430f4d87615d570848aa8

commit r13-5075-g01ea66a6c56e53163d9430f4d87615d570848aa8
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 9 23:41:20 2023 +0100

    c++: Only do maybe_init_list_as_range optimization if
!processing_template_decl [PR108047]

    The last testcase in this patch ICEs, because
    maybe_init_list_as_range -> maybe_init_list_as_array
    calls maybe_constant_init in:
      /* Don't do this if the conversion would be constant.  */
      first = maybe_constant_init (first);
      if (TREE_CONSTANT (first))
        return NULL_TREE;
    but maybe_constant_init shouldn't be called when processing_template_decl.
    While we could replace that call with fold_non_dependent_init, my limited
    understanding is that this is an optimization and even if we don't optimize
    it when processing_template_decl, build_user_type_conversion_1 will be
    called again during instantiation with !processing_template_decl if it is
    every instantiated and we can do the optimization only then.

    2023-01-09  Jakub Jelinek  <jakub@redhat.com>

            PR c++/105838
            PR c++/108047
            PR c++/108266
            * call.cc (maybe_init_list_as_range): Always return NULL_TREE if
            processing_template_decl.

            * g++.dg/tree-ssa/initlist-opt2.C: New test.
            * g++.dg/tree-ssa/initlist-opt3.C: New test.

[Bug c++/105838] [10/11/12/13/14 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #22 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:4d935f52b0d5c00fcc154461b87415ebd8791a94

commit r14-1500-g4d935f52b0d5c00fcc154461b87415ebd8791a94
Author: Jason Merrill <jason@redhat.com>
Date:   Wed Dec 7 11:40:53 2022 -0500

    c++: make initializer_list array static again [PR110070]

    After the maybe_init_list_as_* patches, I noticed that we were putting the
    array of strings into .rodata, but then memcpying it into an automatic
    array, which is pointless; we should be able to use it directly.

    This doesn't happen automatically because TREE_ADDRESSABLE is set (since
    r12-657 for PR100464), and so gimplify_init_constructor won't promote the
    variable to static.  Theoretically we could do escape analysis to recognize
    that the address, though taken, never leaves the function; that would allow
    promotion when we're only using the address for indexing within the
    function, as in initlist-opt2.C.  But this would be a new pass.

    And in initlist-opt1.C, we're passing the array address to another
function,
    so it definitely escapes; it's only safe in this case because it's calling
a
    standard library function that we know only uses it for indexing.  So, a
    flag seems needed.  I first thought to put the flag on the TARGET_EXPR, but
    the VAR_DECL seems more appropriate.

    In a previous revision of the patch I called this flag DECL_NOT_OBSERVABLE,
    but I think DECL_MERGEABLE is a better name, especially if we're going to
    apply it to the backing array of initializer_list, which is observable.  I
    then also check it in places that check for -fmerge-all-constants, so that
    multiple equivalent initializer-lists can also be combined.  And then it
    seemed to make sense for [[no_unique_address]] to have this meaning for
    user-written variables.

    I think the note in [dcl.init.list]/6 intended to allow this kind of
merging
    for initializer_lists, but it didn't actually work; for an explicit array
    with the same initializer, if the address escapes the program could tell
    whether the same variable in two frames have the same address.  P2752 is
    trying to correct this defect, so I'm going to assume that this is the
    intent.

            PR c++/110070
            PR c++/105838

    gcc/ChangeLog:

            * tree.h (DECL_MERGEABLE): New.
            * tree-core.h (struct tree_decl_common): Mention it.
            * gimplify.cc (gimplify_init_constructor): Check it.
            * cgraph.cc (symtab_node::address_can_be_compared_p): Likewise.
            * varasm.cc (categorize_decl_for_section): Likewise.

    gcc/cp/ChangeLog:

            * call.cc (maybe_init_list_as_array): Set DECL_MERGEABLE.
            (convert_like_internal) [ck_list]: Set it.
            (set_up_extended_ref_temp): Copy it.
            * tree.cc (handle_no_unique_addr_attribute): Set it.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/initlist-opt1.C: Check for static array.
            * g++.dg/tree-ssa/initlist-opt2.C: Likewise.
            * g++.dg/tree-ssa/initlist-opt4.C: New test.
            * g++.dg/opt/icf1.C: New test.
            * g++.dg/opt/icf2.C: New test.
            * g++.dg/opt/icf3.C: New test.
            * g++.dg/tree-ssa/array-temp1.C: Revert r12-657 change.

[Bug c++/105838] [10/11/12 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

--- Comment #23 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Jason Merrill <jason@gcc.gnu.org>:

https://gcc.gnu.org/g:2764335bd336f2360d465ffcaa8f2c33f7321ab4

commit r14-1705-g2764335bd336f2360d465ffcaa8f2c33f7321ab4
Author: Jason Merrill <jason@redhat.com>
Date:   Tue Dec 6 18:10:48 2022 -0500

    c++: build initializer_list<string> in a loop [PR105838]

    I previously applied this change in r13-4565 but reverted it due to
    PR108071.  That PR was then fixed by r13-4712, but I didn't re-apply this
    change then because we weren't making the array static; since r14-1500 for
    PR110070 we now make the initializer array static, so let's bring this
back.

    In situations where the maybe_init_list_as_range optimization isn't viable,
    we can build an initializer_list<string> with a loop over a constant array
    of string literals.

    This is represented using a VEC_INIT_EXPR, which required adjusting a
couple
    of places that expected the initializer array to have the same type as the
    target array and fixing build_vec_init not to undo our efforts.

            PR c++/105838

    gcc/cp/ChangeLog:

            * call.cc (convert_like_internal) [ck_list]: Use
            maybe_init_list_as_array.
            * constexpr.cc (cxx_eval_vec_init_1): Init might have
            a different type.
            * tree.cc (build_vec_init_elt): Likewise.
            * init.cc (build_vec_init): Handle from_array from a
            TARGET_EXPR.  Retain TARGET_EXPR of a different type.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/initlist-opt5.C: New test.

[Bug c++/105838] [11/12 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |11.5

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 branch is being closed.

[Bug c++/105838] [11/12 Regression] g++ 12.1.0 runs out of memory or time when building const std::vector of std::strings

[fxcoudert at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105838

Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fxcoudert at gcc dot gnu.org

--- Comment #25 from Francois-Xavier Coudert <fxcoudert at gcc dot gnu.org> ---
The new test (g++.dg/tree-ssa/initlist-opt5.C) fails on darwin. The gimple dump
is like this:

void f (const char * p)
{
  const struct basic_string * retval.0;
  const struct basic_string * D.24981;
  const struct basic_string * D.24982;
  long int D.24983;
  struct allocator D.24824;
  struct initializer_list lst;
  const struct basic_string D.24980[72];

  try
    {
      lst = {};
      lst._M_len = 72;
      D.24981 = &D.24980;
      D.24982 = D.24981;
      D.24983 = 71;
      try
        {
          _4 = D.24982;
          try
            {
              std::allocator<char>::allocator (&D.24824);
              try
                {
                  std::__cxx11::basic_string<char>::basic_string (_4, "aahing",
&D.24824);
                  D.24982 = D.24982 + 32;
                  D.24983 = D.24983 + -1;
                  _5 = D.24982;
                  std::__cxx11::basic_string<char>::basic_string (_5, "aaliis",
&D.24824);
                  D.24982 = D.24982 + 32;
                  D.24983 = D.24983 + -1;
                  _6 = D.24982;
                  std::__cxx11::basic_string<char>::basic_string (_6, "aarrgh",
&D.24824);
                  D.24982 = D.24982 + 32;
                  D.24983 = D.24983 + -1;
                  _7 = D.24982;
[...]
                  std::__cxx11::basic_string<char>::basic_string (_75,
"absent", &D.24824);
                  D.24982 = D.24982 + 32;
                  D.24983 = D.24983 + -1;
                  retval.0 = D.24981;
                  D.24983 = 71;
                  lst._M_array = &D.24980;
                }
              finally
                {
                  std::allocator<char>::~allocator (&D.24824);
                }
            }
          finally
            {
              D.24824 = {CLOBBER(eol)};
            }
        }
      catch
        {
          {
            const struct basic_string * D.24984;

            if (D.24981 != 0B) goto <D.27734>; else goto <D.27735>;
            <D.27734>:
            _1 = 71 - D.24983;
            _2 = (sizetype) _1;
            _3 = _2 * 32;
            D.24984 = D.24981 + _3;
            <D.27736>:
            if (D.24984 == D.24981) goto <D.27737>; else goto <D.27738>;
            <D.27738>:
            D.24984 = D.24984 + 18446744073709551584;
            std::__cxx11::basic_string<char>::~basic_string (D.24984);
            goto <D.27736>;
            <D.27737>:
            goto <D.27739>;
            <D.27735>:
            <D.27739>:
          }
        }
      try
        {
          g (&lst);
        }
      finally
        {
          {
            const struct basic_string * D.24985;

            D.24985 = &D.24980 + 2304;
            <D.27740>:
            if (&D.24980 == D.24985) goto <D.27741>; else goto <D.27742>;
            <D.27742>:
            D.24985 = D.24985 + 18446744073709551584;
            std::__cxx11::basic_string<char>::~basic_string (D.24985);
            goto <D.27740>;
            <D.27741>:
          }
        }
    }
  finally
    {
      lst = {CLOBBER(eol)};
      D.24980 = {CLOBBER(eol)};
    }
}


__attribute__((always_inline))
void std::allocator<char>::allocator (struct allocator * const this)
{
  try
    {
      {
        std::__new_allocator<char>::__new_allocator (this);
        try
          {

          }
        catch
          {
            std::__new_allocator<char>::~__new_allocator (this);
          }
      }
    }
  catch
    {
      <<<eh_must_not_throw (terminate)>>>
    }
}


__attribute__((always_inline))
void std::__new_allocator<char>::__new_allocator (struct __new_allocator *
const this)
{
  try
    {
      {

      }
    }
  catch
    {
      <<<eh_must_not_throw (terminate)>>>
    }
}


__attribute__((always_inline))
void std::allocator<char>::~allocator (struct allocator * const this)
{
  try
    {
      {
        try
          {

          }
        finally
          {
            std::__new_allocator<char>::~__new_allocator (this);
          }
      }
    }
  catch
    {
      <<<eh_must_not_throw (terminate)>>>
    }
}


void std::__new_allocator<char>::~__new_allocator (struct __new_allocator *
const this)
{
  try
    {
      {

      }
    }
  catch
    {
      <<<eh_must_not_throw (terminate)>>>
    }
}