public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
@ 2007-08-13 17:18 Steve Ellcey
  2007-08-13 17:50 ` Ian Lance Taylor
  2007-08-14 14:15 ` Diego Novillo
  0 siblings, 2 replies; 13+ messages in thread
From: Steve Ellcey @ 2007-08-13 17:18 UTC (permalink / raw)
  To: andreasmeier80, dberlin, dnovillo, gcc-patches, iant


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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-13 17:18 Patch for PR tree-optimization/32941, bootstrap comparision failure Steve Ellcey
@ 2007-08-13 17:50 ` Ian Lance Taylor
  2007-08-14 17:25   ` Steve Ellcey
  2007-08-14 18:03   ` Steve Ellcey
  2007-08-14 14:15 ` Diego Novillo
  1 sibling, 2 replies; 13+ messages in thread
From: Ian Lance Taylor @ 2007-08-13 17:50 UTC (permalink / raw)
  To: sje; +Cc: andreasmeier80, dberlin, dnovillo, gcc-patches

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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-13 17:18 Patch for PR tree-optimization/32941, bootstrap comparision failure Steve Ellcey
  2007-08-13 17:50 ` Ian Lance Taylor
@ 2007-08-14 14:15 ` Diego Novillo
  1 sibling, 0 replies; 13+ messages in thread
From: Diego Novillo @ 2007-08-14 14:15 UTC (permalink / raw)
  To: sje; +Cc: andreasmeier80, dberlin, gcc-patches, iant

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.

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-13 17:50 ` Ian Lance Taylor
@ 2007-08-14 17:25   ` Steve Ellcey
  2007-08-14 18:03   ` Steve Ellcey
  1 sibling, 0 replies; 13+ messages in thread
From: Steve Ellcey @ 2007-08-14 17:25 UTC (permalink / raw)
  To: iant; +Cc: andreasmeier80, dberlin, dnovillo, gcc-patches

> 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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-13 17:50 ` Ian Lance Taylor
  2007-08-14 17:25   ` Steve Ellcey
@ 2007-08-14 18:03   ` Steve Ellcey
  1 sibling, 0 replies; 13+ messages in thread
From: Steve Ellcey @ 2007-08-14 18:03 UTC (permalink / raw)
  To: iant; +Cc: andreasmeier80, dberlin, dnovillo, gcc-patches

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) \

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 22:05       ` Daniel Berlin
@ 2007-08-10 22:18         ` Steve Ellcey
  0 siblings, 0 replies; 13+ messages in thread
From: Steve Ellcey @ 2007-08-10 22:18 UTC (permalink / raw)
  To: dberlin; +Cc: novillo, gcc-patches, andreasmeier80

> > 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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 21:58     ` Steve Ellcey
@ 2007-08-10 22:05       ` Daniel Berlin
  2007-08-10 22:18         ` Steve Ellcey
  0 siblings, 1 reply; 13+ messages in thread
From: Daniel Berlin @ 2007-08-10 22:05 UTC (permalink / raw)
  To: Steve Ellcey; +Cc: dnovillo, gcc-patches, andreasmeier80

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.

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 21:45   ` Daniel Berlin
  2007-08-10 21:58     ` Steve Ellcey
@ 2007-08-10 22:00     ` Diego Novillo
  1 sibling, 0 replies; 13+ messages in thread
From: Diego Novillo @ 2007-08-10 22:00 UTC (permalink / raw)
  To: Daniel Berlin; +Cc: sje, gcc-patches, andreasmeier80

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.

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 21:45   ` Daniel Berlin
@ 2007-08-10 21:58     ` Steve Ellcey
  2007-08-10 22:05       ` Daniel Berlin
  2007-08-10 22:00     ` Diego Novillo
  1 sibling, 1 reply; 13+ messages in thread
From: Steve Ellcey @ 2007-08-10 21:58 UTC (permalink / raw)
  To: dberlin; +Cc: dnovillo, sje, gcc-patches, andreasmeier80

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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 16:39 ` Diego Novillo
@ 2007-08-10 21:45   ` Daniel Berlin
  2007-08-10 21:58     ` Steve Ellcey
  2007-08-10 22:00     ` Diego Novillo
  0 siblings, 2 replies; 13+ messages in thread
From: Daniel Berlin @ 2007-08-10 21:45 UTC (permalink / raw)
  To: Diego Novillo; +Cc: sje, gcc-patches, andreasmeier80

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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 15:50 Steve Ellcey
  2007-08-10 16:33 ` Ian Lance Taylor
@ 2007-08-10 16:39 ` Diego Novillo
  2007-08-10 21:45   ` Daniel Berlin
  1 sibling, 1 reply; 13+ messages in thread
From: Diego Novillo @ 2007-08-10 16:39 UTC (permalink / raw)
  To: sje; +Cc: gcc-patches, andreasmeier80

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.

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Patch for PR tree-optimization/32941, bootstrap comparision failure
  2007-08-10 15:50 Steve Ellcey
@ 2007-08-10 16:33 ` Ian Lance Taylor
  2007-08-10 16:39 ` Diego Novillo
  1 sibling, 0 replies; 13+ messages in thread
From: Ian Lance Taylor @ 2007-08-10 16:33 UTC (permalink / raw)
  To: sje; +Cc: gcc-patches, andreasmeier80

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

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Patch for PR tree-optimization/32941, bootstrap comparision failure
@ 2007-08-10 15:50 Steve Ellcey
  2007-08-10 16:33 ` Ian Lance Taylor
  2007-08-10 16:39 ` Diego Novillo
  0 siblings, 2 replies; 13+ messages in thread
From: Steve Ellcey @ 2007-08-10 15:50 UTC (permalink / raw)
  To: gcc-patches; +Cc: andreasmeier80

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.  */

^ permalink raw reply	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2007-08-14 18:03 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-08-13 17:18 Patch for PR tree-optimization/32941, bootstrap comparision failure Steve Ellcey
2007-08-13 17:50 ` Ian Lance Taylor
2007-08-14 17:25   ` Steve Ellcey
2007-08-14 18:03   ` Steve Ellcey
2007-08-14 14:15 ` Diego Novillo
  -- strict thread matches above, loose matches on Subject: below --
2007-08-10 15:50 Steve Ellcey
2007-08-10 16:33 ` Ian Lance Taylor
2007-08-10 16:39 ` Diego Novillo
2007-08-10 21:45   ` Daniel Berlin
2007-08-10 21:58     ` Steve Ellcey
2007-08-10 22:05       ` Daniel Berlin
2007-08-10 22:18         ` Steve Ellcey
2007-08-10 22:00     ` Diego Novillo

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).