From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id E2DCF385828D; Fri, 21 Oct 2022 07:07:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E2DCF385828D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666336058; bh=oAIBSUmS5g149mHJ6WUhyGAatGRgmN/n68znWrOf8LY=; h=From:To:Subject:Date:In-Reply-To:References:From; b=K8aEPBkdcHoHVxFUa7UxSK9JdijdJjXuwG9xiMJPk8DSCxPM4yBcSC1lRoZegRhYn SYHhCR5EFrjH2Awylfu+HkBAPRBBN8eIxn5ggdP920k/qOY3x6/op3MZeUQFOqtkYE H8dzLMFu4xNzvmkcwHgIaUk0lWY3CPepYRTQZ5Ms= From: "rguenth at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue Date: Fri, 21 Oct 2022 07:07:37 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: tree-optimization X-Bugzilla-Version: 11.2.0 X-Bugzilla-Keywords: wrong-code X-Bugzilla-Severity: normal X-Bugzilla-Who: rguenth at gcc dot gnu.org X-Bugzilla-Status: ASSIGNED X-Bugzilla-Resolution: X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org X-Bugzilla-Target-Milestone: 10.5 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: attachments.created 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=3D107323 --- Comment #7 from Richard Biener --- Created attachment 53740 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=3D53740&action=3Dedit tentative patch When implementing that I noticed that the set of DRs we use for versioning = are _not_ enough to break the SCC. Basically I swapped /* Run SCC finding algorithm again, with alias dependence edges skipped. This is to topologically sort partitions according to compilation time known dependence. Note the topological order is stored in the form of pg's post order number. */ num_sccs_no_alias =3D graphds_scc (pg, NULL, pg_skip_alias_edge); gcc_assert (partitions->length () =3D=3D (unsigned) num_sccs_no_al= ias); /* With topological order, we can construct two subgraphs L and R. L contains edge where x < y in terms of post order, while R contains edge where x > y. Edges for compilation time known dependence all fall in R, so we break SCCs by removing all (alias) edges of in subgraph L. */ for_each_edge (pg, pg_collect_alias_ddrs, &cbdata); doing pg_collect_alias_ddrs first and clearing all not collected ->alias_dd= rs so we end up only ignoring those edges we version. For the testcase at hand the patch then ICEs at the assert gcc_assert (partitions->length () =3D=3D (unsigned) num_sccs_no_al= ias); which means that not all SCCs were broken by this. I think the issue is that we do /* Vertices are topologically sorted according to compilation time known dependences, so we can break strong connected components by removing edges of the opposite direction, i.e, edges pointing from vertice with smaller post number to vertice with bigger post number. */ if (g->vertices[i].post < g->vertices[j].post originally we are comparing SCCs of the graph with all edges and the postorder numbers of the graph with all alias_ddr edges removed (and thus no SCCs). That seems unreliable at best. I notice that with the proposed change we change that so the postorder numbers are also for the graph with all edges which means the comment no longer holds. Maybe it also really tries to check i < j and not the postorder numbers. I need to look closer.=