[Bug c++/114480] [12/13/14/15 Regression] g++: internal compiler error: Segmentation fault signal terminated program cc1plus

["cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

--- Comment #32 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Alexander Monakov <amonakov@gcc.gnu.org>:

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

commit r15-628-g4b9e68a6f3b22800a7f12b58ef6b25e3b339bb3c
Author: Alexander Monakov <amonakov@ispras.ru>
Date:   Wed May 15 16:23:17 2024 +0300

    tree-into-ssa: speed up sorting in prune_unused_phi_nodes [PR114480]

    In PR 114480 we are hitting a case where tree-into-ssa scales
    quadratically due to prune_unused_phi_nodes doing O(N log N)
    work for N basic blocks, for each variable individually.
    Sorting the 'defs' array is especially costly.

    It is possible to assist gcc_qsort by laying out dfs_out entries
    in the reverse order in the 'defs' array, starting from its tail.
    This is not always a win (in fact it flips most of 7-element qsorts
    in this testcase from 9 comparisons (best case) to 15 (worst case)),
    but overall it helps on the testcase and on libstdc++ build.
    On the testcase we go from 1.28e9 comparator invocations to 1.05e9,
    on libstdc++ from 2.91e6 to 2.84e6.

    gcc/ChangeLog:

            PR c++/114480
            * tree-into-ssa.cc (prune_unused_phi_nodes): Add dfs_out entries
            to the 'defs' array in the reverse order.