Re: [Bug bootstrap/36908] bootstrap forever with BOOT_CFLAGS="-O2 -ftree-loop-distribution"

["Sebastian Pop" <sebpop at gmail dot com>]

> Sebastian, can you please look at this?

Sorry for having missed this bug.  The problem here is that we end
with two identical loops, as we copy almost all the statements in both
loops.  The attached patch solves the problem by counting the number
of memory read and write operations per partition and compares it to
the total number of memory operations in the Reduced Dependence Graph.
Loop distribution is stopped when one of the partitions contains all
the memory ops.

Okay for trunk once it finishes regstrap?

Thanks,
Sebastian

	PR tree-optimization/36908
	* testsuite/gcc.dg/tree-ssa/pr36908.c: New.
	* tree-loop-distribution.c (number_of_rw_in_rdg): New.
	(number_of_rw_in_partition): New.
	(partition_contains_all_rw): New.
	(ldist_gen): Do not distribute when one of the partitions
	contains all the memory operations.

Index: tree-loop-distribution.c
===================================================================
--- tree-loop-distribution.c	(revision 141245)
+++ tree-loop-distribution.c	(working copy)
@@ -945,6 +945,64 @@ debug_rdg_partitions (VEC (bitmap, heap)
   dump_rdg_partitions (stderr, partitions);
 }
 
+/* Returns the number of read and write operations in the RDG.  */
+
+static int
+number_of_rw_in_rdg (struct graph *rdg)
+{
+  int i, res = 0;
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    {
+      if (RDG_MEM_WRITE_STMT (rdg, i))
+	++res;
+
+      if (RDG_MEM_READS_STMT (rdg, i))
+	++res;
+    }
+
+  return res;
+}
+
+/* Returns the number of read and write operations in a PARTITION of
+   the RDG.  */
+
+static int
+number_of_rw_in_partition (struct graph *rdg, bitmap partition)
+{
+  int res = 0;
+  unsigned i;
+  bitmap_iterator ii;
+
+  EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
+    {
+      if (RDG_MEM_WRITE_STMT (rdg, i))
+	++res;
+
+      if (RDG_MEM_READS_STMT (rdg, i))
+	++res;
+    }
+
+  return res;
+}
+
+/* Returns true when one of the PARTITIONS contains all the read or
+   write operations of RDG.  */
+
+static bool
+partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
+{
+  int i;
+  bitmap partition;
+  int nrw = number_of_rw_in_rdg (rdg);
+
+  for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
+    if (nrw == number_of_rw_in_partition (rdg, partition))
+      return true;
+
+  return false;
+}
+
 /* Generate code from STARTING_VERTICES in RDG.  Returns the number of
    distributed loops.  */
 
@@ -992,7 +1050,8 @@ ldist_gen (struct loop *loop, struct gra
   BITMAP_FREE (processed);
   nbp = VEC_length (bitmap, partitions);
 
-  if (nbp <= 1)
+  if (nbp <= 1
+      || partition_contains_all_rw (rdg, partitions))
     goto ldist_done;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
Index: testsuite/gcc.dg/tree-ssa/pr36908.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr36908.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/pr36908.c	(revision 0)
@@ -0,0 +1,65 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-loop-distribution" } */
+#define NULL ((void *)0)
+
+typedef unsigned int size_t;
+extern void *calloc(size_t nelem, size_t elsize);
+extern void printf (char*, ...);
+
+typedef struct alt_state *alt_state_t;
+typedef struct state *state_t;
+
+struct alt_state
+{
+  alt_state_t next_alt_state;
+};
+
+static alt_state_t first_free_alt_state = NULL;
+
+static void
+free_alt_state (alt_state_t alt_state)
+{
+  if (alt_state == NULL)
+    return;
+  alt_state->next_alt_state = first_free_alt_state;
+  first_free_alt_state = alt_state;
+}
+
+/* The function frees list started with node ALT_STATE_LIST.  */
+static void
+free_alt_states (alt_state_t alt_states_list)
+{
+  alt_state_t curr_alt_state;
+  alt_state_t next_alt_state;
+
+  for (curr_alt_state = alt_states_list;
+       curr_alt_state != NULL;
+       curr_alt_state = next_alt_state)
+    {
+      next_alt_state = curr_alt_state->next_alt_state;
+      free_alt_state (curr_alt_state);
+    }
+}
+
+int 
+main (void)
+{
+  int i;
+  alt_state_t state, act_state;
+
+  act_state = state = calloc (1, sizeof (struct alt_state));
+  for (i = 0; i < 2; i ++)
+  {
+    act_state->next_alt_state = calloc (1, sizeof (struct alt_state));
+    act_state = act_state->next_alt_state;
+  }
+
+  free_alt_states (state);
+
+  for (act_state = first_free_alt_state;
+       act_state != NULL;
+       act_state = act_state->next_alt_state)
+       printf ("going from %p to %p\n", act_state, act_state->next_alt_state);
+
+  return 0;
+}