From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 5FDEE3858C98; Thu, 4 Apr 2024 18:41:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5FDEE3858C98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1712256109; bh=FBpbRXU36UlQv5CezSL3UCEOWZaAt9+GLWO8PkAx/E4=; h=From:To:Subject:Date:In-Reply-To:References:From; b=iBq1mrzlE+DGHS/ROk9nhFlsKAvxSFK3ObjDlc2ZxD/ua/Sk7GmkYCpj8svEMAcB3 lvypxZaLpSM63a/SWrp/4wZJZWt+l5eY1msXyB4KQMKribTr5+IQh2p0cOYiqoZsQZ 8Lh+q8wcbo3x/qWMs2Zs+4Key+kT9nvLflFhuh4o= From: "amonakov at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug c++/114480] g++: internal compiler error: Segmentation fault signal terminated program cc1plus Date: Thu, 04 Apr 2024 18:41:46 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: c++ X-Bugzilla-Version: 11.4.0 X-Bugzilla-Keywords: compile-time-hog, memory-hog, ra X-Bugzilla-Severity: normal X-Bugzilla-Who: amonakov at gcc dot gnu.org X-Bugzilla-Status: ASSIGNED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D114480 --- Comment #20 from Alexander Monakov --- (note that if you uninclude the testcase and compile with -fno-exceptions i= t'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 rough= ly linear fashion up to 23437 on the 12294'th invocation. Hence this first pha= se 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!=