[PATCH][1/2] Fix PR62291

[Richard Biener <rguenther at suse dot de>]

This is a first patch towards fixing PR62291 - it removes the
need of having AVAIL_OUT computed for all blocks during
compute_[partial_]antic_aux (or 'clean').  NAMEs are
available by construction and there is no need to check that
(changing the code to an assert passes bootstrap as expected).

I've noticed that sorted_array_from_bitmap_set can be sped up
so I've sneaked that change in with this patch.

Boostrapped (the version with the assert) on x86_64-unknown-linux-gnu,
bootstrap and regtest ongoing for this final variant.

The second patch (once done) will refactor insertion phase
to do a dominator walk similar to what elimination does
computing AVAIL_OUT on-the-fly (and only keeping it live
for a single block).  It's a bit more complicated than
for elimination as insertion looks at a block and all its
predecessors, it's also a bit more costly as we iterate
insertion.  It's also more costly because computing
AVAIL_OUT on-the-fly requires looking at all statements
which insertion currently doesn't do at all.
So I've not yet settled on a final idea how to best re-factor it,
eventually insertion and elimination can be merged (and then
still iterate(?)).

Ideas welcome ;)

Meanwhile the following patch is a strict improvement to
at least compile-time.

Thanks,
Richard.

2014-08-29  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/62291
	* tree-ssa-pre.c (sorted_array_from_bitmap_set): Reserve
	exactly the vector size needed and use quick_push.
	(phi_translate_1): Adjust comment.
	(valid_in_sets): Remove block argument and remove pointless
	checking of NAMEs.
	(dependent_clean): Adjust for removal of block argument.
	(clean): Likewise.
	(compute_antic_aux): Likewise.
	(compute_partial_antic_aux): Likewise.

Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 214680)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -719,8 +719,8 @@ sorted_array_from_bitmap_set (bitmap_set
   bitmap_iterator bi, bj;
   vec<pre_expr> result;
 
-  /* Pre-allocate roughly enough space for the array.  */
-  result.create (bitmap_count_bits (&set->values));
+  /* Pre-allocate enough space for the array.  */
+  result.create (bitmap_count_bits (&set->expressions));
 
   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
     {
@@ -738,7 +738,7 @@ sorted_array_from_bitmap_set (bitmap_set
       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
 	{
 	  if (bitmap_bit_p (&set->expressions, j))
-	    result.safe_push (expression_for_id (j));
+	    result.quick_push (expression_for_id (j));
         }
     }
 
@@ -1736,8 +1736,9 @@ phi_translate_1 (pre_expr expr, bitmap_s
 
 	    return get_or_alloc_expr_for_name (def);
 	  }
-	/* Otherwise return it unchanged - it will get cleaned if its
-	   value is not available in PREDs AVAIL_OUT set of expressions.  */
+	/* Otherwise return it unchanged - it will get removed if its
+	   value is not available in PREDs AVAIL_OUT set of expressions
+	   by the subtraction of TMP_GEN.  */
 	return expr;
       }
 
@@ -1976,14 +1977,14 @@ op_valid_in_sets (bitmap_set_t set1, bit
    For loads/calls, we also see if the vuse is killed in this block.  */
 
 static bool
-valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
-	       basic_block block)
+valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
 {
   switch (expr->kind)
     {
     case NAME:
-      return bitmap_find_leader (AVAIL_OUT (block),
-				 get_expr_value_id (expr)) != NULL;
+      /* By construction all NAMEs are available.  Non-available
+	 NAMEs are removed by subtracting TMP_GEN from the sets.  */
+      return true;
     case NARY:
       {
 	unsigned int i;
@@ -2021,7 +2022,7 @@ valid_in_sets (bitmap_set_t set1, bitmap
    PA_IN.  */
 
 static void
-dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
+dependent_clean (bitmap_set_t set1, bitmap_set_t set2)
 {
   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
   pre_expr expr;
@@ -2029,7 +2030,7 @@ dependent_clean (bitmap_set_t set1, bitm
 
   FOR_EACH_VEC_ELT (exprs, i, expr)
     {
-      if (!valid_in_sets (set1, set2, expr, block))
+      if (!valid_in_sets (set1, set2, expr))
 	bitmap_remove_from_set (set1, expr);
     }
   exprs.release ();
@@ -2040,7 +2041,7 @@ dependent_clean (bitmap_set_t set1, bitm
    in SET.  */
 
 static void
-clean (bitmap_set_t set, basic_block block)
+clean (bitmap_set_t set)
 {
   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set);
   pre_expr expr;
@@ -2048,7 +2049,7 @@ clean (bitmap_set_t set, basic_block blo
 
   FOR_EACH_VEC_ELT (exprs, i, expr)
     {
-      if (!valid_in_sets (set, NULL, expr, block))
+      if (!valid_in_sets (set, NULL, expr))
 	bitmap_remove_from_set (set, expr);
     }
   exprs.release ();
@@ -2250,7 +2251,7 @@ compute_antic_aux (basic_block block, bo
     bitmap_value_insert_into_set (ANTIC_IN (block),
 				  expression_for_id (bii));
 
-  clean (ANTIC_IN (block), block);
+  clean (ANTIC_IN (block));
 
   if (!bitmap_set_equal (old, ANTIC_IN (block)))
     {
@@ -2405,7 +2406,7 @@ compute_partial_antic_aux (basic_block b
   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
 
-  dependent_clean (PA_IN (block), ANTIC_IN (block), block);
+  dependent_clean (PA_IN (block), ANTIC_IN (block));
 
   if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
     {