[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" <gcc-bugzilla@gcc.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