[Bug tree-optimization/107323] [10/11/12 Regression] Loop distribute issue

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 53740
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53740&action=edit
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 = graphds_scc (pg, NULL, pg_skip_alias_edge);
         gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias);
         /* With topological order, we can construct two subgraphs L and R.
            L contains edge <x, y> where x < y in terms of post order, while
            R contains edge <x, y> 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_ddrs
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 () == (unsigned) num_sccs_no_alias);

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.