Patch for PR tree-optimization/32941, bootstrap comparision failure

Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

This patch fixes PR tree-optimization/32941, a bootstrap comparision
failure.  Currently we sort the goto_queue in tree-eh.c using qsort and
search it with bsearch.  Because qsort is an unstable sort and we are
sorting on addresses we can get different orderings during different
bootstrap passes, resulting in the comparision failure.

This patch removes the sort and replaces the bsearch call with a simple
linear search.  The obvious concern with this is compile time
performance but during a bootstrap the largest size goto_queue I saw was
7 elements and while compiling the C++ SPEC2006 benchmarks, the largest
size I saw was 30.

Given these relatively small sizes for the goto_queue, I think using a
linear search will not result in any compile time change or may actually
be faster since 99% of the time we search the queue the size is 1.

Tested with no regressions.  OK for checkin?

Steve Ellcey
sje@cup.hp.com


2007-08-10  Steve Ellcey  <sje@cup.hp.com>

	PR tree-optimization/32941
	* tree-eh.c (goto_queue_cmp): Remove.
	(find_goto_replacement): Change bsearch call to linear search.
	(lower_try_finally): Remove qsort call.


Index: tree-eh.c
===================================================================
--- tree-eh.c	(revision 127288)
+++ tree-eh.c	(working copy)
@@ -338,29 +338,17 @@ struct leh_tf_state
 static void lower_eh_filter (struct leh_state *, tree *);
 static void lower_eh_constructs_1 (struct leh_state *, tree *);
 
-/* Comparison function for qsort/bsearch.  We're interested in
-   searching goto queue elements for source statements.  */
-
-static int
-goto_queue_cmp (const void *x, const void *y)
-{
-  tree a = ((const struct goto_queue_node *)x)->stmt;
-  tree b = ((const struct goto_queue_node *)y)->stmt;
-  return (a == b ? 0 : a < b ? -1 : 1);
-}
-
 /* Search for STMT in the goto queue.  Return the replacement,
    or null if the statement isn't in the queue.  */
 
 static tree
 find_goto_replacement (struct leh_tf_state *tf, tree stmt)
 {
-  struct goto_queue_node tmp, *ret;
-  tmp.stmt = stmt;
-  ret = (struct goto_queue_node *)
-     bsearch (&tmp, tf->goto_queue, tf->goto_queue_active,
-		 sizeof (struct goto_queue_node), goto_queue_cmp);
-  return (ret ? ret->repl_stmt : NULL);
+  unsigned int i;
+  for (i = 0; i < tf->goto_queue_active; i++)
+    if (tf->goto_queue[i].stmt == stmt)
+      return tf->goto_queue[i].repl_stmt;
+  return NULL;
 }
 
 /* A subroutine of replace_goto_queue_1.  Handles the sub-clauses of a
@@ -1371,11 +1359,6 @@ lower_try_finally (struct leh_state *sta
       honor_protect_cleanup_actions (state, &this_state, &this_tf);
     }
 
-  /* Sort the goto queue for efficient searching later.  */
-  if (this_tf.goto_queue_active > 1)
-    qsort (this_tf.goto_queue, this_tf.goto_queue_active,
-	   sizeof (struct goto_queue_node), goto_queue_cmp);
-
   /* Determine how many edges (still) reach the finally block.  Or rather,
      how many destinations are reached by the finally block.  Use this to
      determine how we process the finally block itself.  */

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Ian Lance Taylor]

Steve Ellcey <sje@cup.hp.com> writes:

> This patch fixes PR tree-optimization/32941, a bootstrap comparision
> failure.  Currently we sort the goto_queue in tree-eh.c using qsort and
> search it with bsearch.  Because qsort is an unstable sort and we are
> sorting on addresses we can get different orderings during different
> bootstrap passes, resulting in the comparision failure.
> 
> This patch removes the sort and replaces the bsearch call with a simple
> linear search.  The obvious concern with this is compile time
> performance but during a bootstrap the largest size goto_queue I saw was
> 7 elements and while compiling the C++ SPEC2006 benchmarks, the largest
> size I saw was 30.
> 
> Given these relatively small sizes for the goto_queue, I think using a
> linear search will not result in any compile time change or may actually
> be faster since 99% of the time we search the queue the size is 1.

I don't think this is a good idea.  I think it will significantly hurt
compiler time performance on some machine generated C++ code.

I think the idea of not sorting the queue makes sense.  I just think
we need to augment your patch by adding a pointer_map which maps from
statements to queue elements.  That is, maybe_record_in_goto_queue
will call pointer_map_insert with STMT, and find_goto_replacement will
call pointer_map_contains.

Ian

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Diego Novillo]

On 8/10/07 9:49 AM, Steve Ellcey wrote:

> 	PR tree-optimization/32941
> 	* tree-eh.c (goto_queue_cmp): Remove.
> 	(find_goto_replacement): Change bsearch call to linear search.
> 	(lower_try_finally): Remove qsort call.

How about a compromise?  Use the linear search if the queue is < ~100.
And do the sort otherwise.  I'd like to avoid a future compile time PR
with huge EH graphs.

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Daniel Berlin]

On 8/10/07, Diego Novillo <dnovillo@google.com> wrote:
> On 8/10/07 9:49 AM, Steve Ellcey wrote:
>
> >       PR tree-optimization/32941
> >       * tree-eh.c (goto_queue_cmp): Remove.
> >       (find_goto_replacement): Change bsearch call to linear search.
> >       (lower_try_finally): Remove qsort call.
>
> How about a compromise?  Use the linear search if the queue is < ~100.
> And do the sort otherwise.  I'd like to avoid a future compile time PR
> with huge EH graphs.
>

Or uh, why not just make qsort not sort on the addresses?
Can't you add uid's to the statements based on the order we see them,
and just sort on that?

This is what a few other passes do.

add an id

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

Daniel Berlin wrote:

> Or uh, why not just make qsort not sort on the addresses?
> Can't you add uid's to the statements based on the order we see them,
> and just sort on that?
> 
> This is what a few other passes do.
> 
> add an id

But the stmt field in the goto_queue_node is a tree, adding an id would
mean adding an id to the general tree structure (I think).  Are we willing
to add that kind of space?  Or are the tree's pointed to by the goto_queue
always a particular type so that we could add it to one subtype of tree?

Steve Ellcey
sje@cup.hp.com

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Daniel Berlin]

On 8/10/07, Steve Ellcey <sje@cup.hp.com> wrote:
> Daniel Berlin wrote:
>
> > Or uh, why not just make qsort not sort on the addresses?
> > Can't you add uid's to the statements based on the order we see them,
> > and just sort on that?
> >
> > This is what a few other passes do.
> >
> > add an id
>
> But the stmt field in the goto_queue_node is a tree, adding an id would
> mean adding an id to the general tree structure (I think).  Are we willing
> to add that kind of space?

see stmt_ann->uid :)

It's for your user for these sorts of things.

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

> > But the stmt field in the goto_queue_node is a tree, adding an id would
> > mean adding an id to the general tree structure (I think).  Are we willing
> > to add that kind of space?
> 
> see stmt_ann->uid :)
> 
> It's for your user for these sorts of things.

I see.  After looking at pointer-set.c I think I will try Ian's idea of
using a pointer map and see if I can make things work that way.  Then we
can skip the sorting and use a hash for the lookup.

Steve Ellcey
sje@cup.hp.com

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Diego Novillo]

On 8/10/07 3:44 PM, Daniel Berlin wrote:

> Or uh, why not just make qsort not sort on the addresses?
> Can't you add uid's to the statements based on the order we see them,
> and just sort on that?

I was trying to avoid sorting at all as qsort/bsearch is slower than
linear search when you only have a handful of entries.  Sorting on a UID
will require the extra pass pawing through everything and adding an ID.
But it's not too bad, so I'm OK with that too.

Ian's suggestion of using a pointer map should work as well.

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

Here is a new patch for PR tree-optimization/32941, the bootstrap
comparision failure.  I am still testing it for regressions but I
thought I would send it out for comments while testing.  Rather than
create a pointer map for all cases, and add entries while putting things
in the goto_queue, I left the insert routine alone, and then when
searching (not done until after all elements have been added), I either
do a linear search if the list is small or I create a pointer map and
use it for searching on that and subsequent calls.  This avoids creating
a pointer map in 99% of the cases.  In this patch, I set
LARGE_GOTO_QUEUE to 2 in order to force the use of pointer maps while I
test it, in the final patch I thought about setting it to 50.

What do people think about the approach?


Steve Ellcey
sje@cup.hp.com


2007-08-13  Steve Ellcey  <sje@cup.hp.com>

	PR tree-optimization/32941
	* tree-eh.c (struct leh_tf_state): Add goto_queue_map field.
	(goto_queue_cmp): Remove.
	(find_goto_replacement): Change search method.
	(maybe_record_in_goto_queue): Add assert.
	(lower_try_finally): Remove qsort call, add pointer_map_destroy call.


Index: tree-eh.c
===================================================================
--- tree-eh.c	(revision 127280)
+++ tree-eh.c	(working copy)
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  
 #include "langhooks.h"
 #include "ggc.h"
 #include "toplev.h"
+#include "pointer-set.h"
 
 \f
 /* Nonzero if we are using EH to handle cleanups.  */
@@ -311,6 +312,9 @@ struct leh_tf_state
   size_t goto_queue_size;
   size_t goto_queue_active;
 
+  /* Pointer map to help in searching qoto_queue when it is large.  */
+  struct pointer_map_t *goto_queue_map;
+
   /* The set of unique labels seen as entries in the goto queue.  */
   VEC(tree,heap) *dest_array;
 
@@ -338,29 +342,44 @@ struct leh_tf_state
 static void lower_eh_filter (struct leh_state *, tree *);
 static void lower_eh_constructs_1 (struct leh_state *, tree *);
 
-/* Comparison function for qsort/bsearch.  We're interested in
-   searching goto queue elements for source statements.  */
-
-static int
-goto_queue_cmp (const void *x, const void *y)
-{
-  tree a = ((const struct goto_queue_node *)x)->stmt;
-  tree b = ((const struct goto_queue_node *)y)->stmt;
-  return (a == b ? 0 : a < b ? -1 : 1);
-}
-
 /* Search for STMT in the goto queue.  Return the replacement,
    or null if the statement isn't in the queue.  */
 
+#define LARGE_GOTO_QUEUE 2
+
 static tree
 find_goto_replacement (struct leh_tf_state *tf, tree stmt)
 {
-  struct goto_queue_node tmp, *ret;
-  tmp.stmt = stmt;
-  ret = (struct goto_queue_node *)
-     bsearch (&tmp, tf->goto_queue, tf->goto_queue_active,
-		 sizeof (struct goto_queue_node), goto_queue_cmp);
-  return (ret ? ret->repl_stmt : NULL);
+  unsigned int i;
+  void **slot;
+
+  if (tf->goto_queue_active < LARGE_GOTO_QUEUE)
+    {
+      for (i = 0; i < tf->goto_queue_active; i++)
+	if (tf->goto_queue[i].stmt == stmt)
+	  return tf->goto_queue[i].repl_stmt;
+      return NULL;
+    }
+
+  /* If we have a large number of entries in the goto_queue, create a
+     pointer map and use that for searching.  */
+
+  if (!tf->goto_queue_map)
+    {
+      tf->goto_queue_map = pointer_map_create ();
+      for (i = 0; i < tf->goto_queue_active; i++)
+	{
+	  void **slot = pointer_map_insert (tf->goto_queue_map, tf->goto_queue[i].stmt);
+          gcc_assert (*slot == NULL);
+	  *slot = (void *) &tf->goto_queue[i];
+	}
+    }
+
+  slot = pointer_map_contains (tf->goto_queue_map, stmt);
+  if (slot != NULL)
+    return (((struct goto_queue_node *) slot)->repl_stmt);
+
+  return NULL;
 }
 
 /* A subroutine of replace_goto_queue_1.  Handles the sub-clauses of a
@@ -519,6 +538,8 @@ maybe_record_in_goto_queue (struct leh_s
       gcc_unreachable ();
     }
 
+  gcc_assert (!tf->goto_queue_map);
+
   active = tf->goto_queue_active;
   size = tf->goto_queue_size;
   if (active >= size)
@@ -1371,11 +1392,6 @@ lower_try_finally (struct leh_state *sta
       honor_protect_cleanup_actions (state, &this_state, &this_tf);
     }
 
-  /* Sort the goto queue for efficient searching later.  */
-  if (this_tf.goto_queue_active > 1)
-    qsort (this_tf.goto_queue, this_tf.goto_queue_active,
-	   sizeof (struct goto_queue_node), goto_queue_cmp);
-
   /* Determine how many edges (still) reach the finally block.  Or rather,
      how many destinations are reached by the finally block.  Use this to
      determine how we process the finally block itself.  */
@@ -1415,6 +1431,8 @@ lower_try_finally (struct leh_state *sta
   VEC_free (tree, heap, this_tf.dest_array);
   if (this_tf.goto_queue)
     free (this_tf.goto_queue);
+  if (this_tf.goto_queue_map)
+    pointer_map_destroy (this_tf.goto_queue_map);
 }
 
 /* A subroutine of lower_eh_constructs_1.  Lower a TRY_CATCH_EXPR with a

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Ian Lance Taylor]

Steve Ellcey <sje@cup.hp.com> writes:

> 2007-08-13  Steve Ellcey  <sje@cup.hp.com>
> 
> 	PR tree-optimization/32941
> 	* tree-eh.c (struct leh_tf_state): Add goto_queue_map field.
> 	(goto_queue_cmp): Remove.
> 	(find_goto_replacement): Change search method.
> 	(maybe_record_in_goto_queue): Add assert.
> 	(lower_try_finally): Remove qsort call, add pointer_map_destroy call.

This is OK if it passes testing.

> +#define LARGE_GOTO_QUEUE 2

I think your proposed value of 50 is too high.  This is an N squared
algorithm.  I would go for something more like 20.

Ian

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

> This is OK if it passes testing.
> 
> > +#define LARGE_GOTO_QUEUE 2
> 
> I think your proposed value of 50 is too high.  This is an N squared
> algorithm.  I would go for something more like 20.
> 
> Ian

I fixed one bug in my last patch (forgot to dereference slot before
using it after the call to pointer_map_contains) and testing on IA64
HP-UX and Linux had no regressions after that.  I also changed the value
of LARGE_GOTO_QUEUE to 20.  Here is the final patch.  I will go ahead
and check it in.

Steve Ellcey
sje@cup.hp.com


2007-08-13  Steve Ellcey  <sje@cup.hp.com>

	PR tree-optimization/32941
	* tree-eh.c (struct leh_tf_state): Add goto_queue_map field.
	(goto_queue_cmp): Remove.
	(find_goto_replacement): Change search method.
	(maybe_record_in_goto_queue): Add assert.
	(lower_try_finally): Remove qsort call, add pointer_map_destroy call.


Index: tree-eh.c
===================================================================
--- tree-eh.c	(revision 127403)
+++ tree-eh.c	(working copy)
@@ -36,6 +36,7 @@ along with GCC; see the file COPYING3.  
 #include "langhooks.h"
 #include "ggc.h"
 #include "toplev.h"
+#include "pointer-set.h"
 
 \f
 /* Nonzero if we are using EH to handle cleanups.  */
@@ -311,6 +312,9 @@ struct leh_tf_state
   size_t goto_queue_size;
   size_t goto_queue_active;
 
+  /* Pointer map to help in searching qoto_queue when it is large.  */
+  struct pointer_map_t *goto_queue_map;
+
   /* The set of unique labels seen as entries in the goto queue.  */
   VEC(tree,heap) *dest_array;
 
@@ -338,29 +342,44 @@ struct leh_tf_state
 static void lower_eh_filter (struct leh_state *, tree *);
 static void lower_eh_constructs_1 (struct leh_state *, tree *);
 
-/* Comparison function for qsort/bsearch.  We're interested in
-   searching goto queue elements for source statements.  */
-
-static int
-goto_queue_cmp (const void *x, const void *y)
-{
-  tree a = ((const struct goto_queue_node *)x)->stmt;
-  tree b = ((const struct goto_queue_node *)y)->stmt;
-  return (a == b ? 0 : a < b ? -1 : 1);
-}
-
 /* Search for STMT in the goto queue.  Return the replacement,
    or null if the statement isn't in the queue.  */
 
+#define LARGE_GOTO_QUEUE 20
+
 static tree
 find_goto_replacement (struct leh_tf_state *tf, tree stmt)
 {
-  struct goto_queue_node tmp, *ret;
-  tmp.stmt = stmt;
-  ret = (struct goto_queue_node *)
-     bsearch (&tmp, tf->goto_queue, tf->goto_queue_active,
-		 sizeof (struct goto_queue_node), goto_queue_cmp);
-  return (ret ? ret->repl_stmt : NULL);
+  unsigned int i;
+  void **slot;
+
+  if (tf->goto_queue_active < LARGE_GOTO_QUEUE)
+    {
+      for (i = 0; i < tf->goto_queue_active; i++)
+	if (tf->goto_queue[i].stmt == stmt)
+	  return tf->goto_queue[i].repl_stmt;
+      return NULL;
+    }
+
+  /* If we have a large number of entries in the goto_queue, create a
+     pointer map and use that for searching.  */
+
+  if (!tf->goto_queue_map)
+    {
+      tf->goto_queue_map = pointer_map_create ();
+      for (i = 0; i < tf->goto_queue_active; i++)
+	{
+	  slot = pointer_map_insert (tf->goto_queue_map, tf->goto_queue[i].stmt);
+          gcc_assert (*slot == NULL);
+	  *slot = (void *) &tf->goto_queue[i];
+	}
+    }
+
+  slot = pointer_map_contains (tf->goto_queue_map, stmt);
+  if (slot != NULL)
+    return (((struct goto_queue_node *) *slot)->repl_stmt);
+
+  return NULL;
 }
 
 /* A subroutine of replace_goto_queue_1.  Handles the sub-clauses of a
@@ -519,6 +538,8 @@ maybe_record_in_goto_queue (struct leh_s
       gcc_unreachable ();
     }
 
+  gcc_assert (!tf->goto_queue_map);
+
   active = tf->goto_queue_active;
   size = tf->goto_queue_size;
   if (active >= size)
@@ -1371,11 +1392,6 @@ lower_try_finally (struct leh_state *sta
       honor_protect_cleanup_actions (state, &this_state, &this_tf);
     }
 
-  /* Sort the goto queue for efficient searching later.  */
-  if (this_tf.goto_queue_active > 1)
-    qsort (this_tf.goto_queue, this_tf.goto_queue_active,
-	   sizeof (struct goto_queue_node), goto_queue_cmp);
-
   /* Determine how many edges (still) reach the finally block.  Or rather,
      how many destinations are reached by the finally block.  Use this to
      determine how we process the finally block itself.  */
@@ -1415,6 +1431,8 @@ lower_try_finally (struct leh_state *sta
   VEC_free (tree, heap, this_tf.dest_array);
   if (this_tf.goto_queue)
     free (this_tf.goto_queue);
+  if (this_tf.goto_queue_map)
+    pointer_map_destroy (this_tf.goto_queue_map);
 }
 
 /* A subroutine of lower_eh_constructs_1.  Lower a TRY_CATCH_EXPR with a

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Steve Ellcey]

I forgot that I modified Makefile.in too in order to make tree-eh.o
dependent on pointer-set.h.  I will add that change in to my patch when
I do the checkin.

Steve Ellcey
sje@cup.hp.com


[hpsje] $ svn diff Makefile.in
Index: Makefile.in
===================================================================
--- Makefile.in (revision 127403)
+++ Makefile.in (working copy)
@@ -2099,7 +2099,7 @@ tree-ssa-operands.o : tree-ssa-operands.
    coretypes.h langhooks.h $(IPA_REFERENCE_H)
 tree-eh.o : tree-eh.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_H) $(FLAGS_H) $(FUNCTION_H) except.h langhooks.h \
-   $(GGC_H) tree-pass.h coretypes.h $(TIMEVAR_H) $(TM_P_H) \
+   $(GGC_H) tree-pass.h coretypes.h $(TIMEVAR_H) $(TM_P_H) pointer-set.h \
    $(TREE_DUMP_H) $(TREE_INLINE_H) tree-iterator.h toplev.h
 tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \

Re: Patch for PR tree-optimization/32941, bootstrap comparision failure

[Diego Novillo]

On 8/13/07 11:10 AM, Steve Ellcey wrote:

> What do people think about the approach?

Looks fine to me.  50 may be a bit too large, but I'm not really sure.