[Bug c++/114480] g++: internal compiler error: Segmentation fault signal terminated program cc1plus

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

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

--- Comment #20 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
(note that if you uninclude the testcase and compile with -fno-exceptions it's
much faster)

On the smaller testcase from comment 14, prune_unused_phi_nodes invokes
gcc_qsort 53386 times. There are two distinct phases.

In the first phase, the count of struct dom_dfsnum to sort grows in a roughly
linear fashion up to 23437 on the 12294'th invocation. Hence this first phase
is quadratic in the overall number of processed dom_dfsnum-s.

In the second phase, it almost always sorts exactly 7 elements for the
remaining ~41000 invocations.

The number of pairwise comparisons performed by gcc_qsort is approximately
(n+1)*(log_2(n)-1), which results in 1.8e9 comparisons overall for the 53386
invocations. perf shows 10.9e9 cycles spent under gcc_qsort, i.e. 6 cycles per
comparison, which looks about right. It's possible to reduce that further by
switching from classic to bidirectional merge, and using cmovs instead of
bitwise arithmetic for branchless selects.

> I'll note the swapping of 8 bytes is a bit odd and it seems to be
> if-converted, thus always doing a write.

That is not a swap. That's the merge step of a mergesort, we are taking the
smaller element from the heads of two arrays and moving it to the tail of a
third array.

Basically there's quadratic behavior in tree-into-ssa, gcc_qsort shows
relatively higher on the profile because the log_2(n) factor becomes
noticeable.

Hope that helps!