[patch] Ping patch for [Bug bootstrap/36908] bootstrap forever with BOOT_CFLAGS="-O2 -ftree-loop-distribution"

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

Hi,

Here is the fix for this bug on loop distribution.

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.

Regstrapped on amd64-linux.
Okay for trunk?

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 *foo(size_t nelem, size_t elsize);
+extern void bar (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 = foo (1, sizeof (struct alt_state));
+  for (i = 0; i < 2; i ++)
+  {
+    act_state->next_alt_state = foo (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)
+       bar ("going from %p to %p\n", act_state, act_state->next_alt_state);
+
+  return 0;
+}