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

[Steve Ellcey <sje@cup.hp.com>]

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