re PR middle-end/54146 (Very slow compile with attribute((flatten)))

2012-08-14  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/54146
	* tree-ssa-pre.c (do_regular_insertion): Use a VEC
	indexed by pred edge index for avail.
	(do_partial_partial_insertion): Likewise.
	(insert_into_preds_of_block): Adjust.

From-SVN: r190382

1 files changed, 30 insertions, 29 deletions

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index b477540..83dded2 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3188,7 +3188,7 @@ inhibit_phi_insertion (basic_block bb, pre_expr expr)
 
 static bool
 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
-			    pre_expr *avail)
+			    VEC(pre_expr, heap) *avail)
 {
   pre_expr expr = expression_for_id (exprnum);
   pre_expr newphi;
@@ -3229,7 +3229,7 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
       gimple_seq stmts = NULL;
       tree builtexpr;
       bprime = pred->src;
-      eprime = avail[bprime->index];
+      eprime = VEC_index (pre_expr, avail, pred->dest_idx);
 
       if (eprime->kind != NAME && eprime->kind != CONSTANT)
 	{
@@ -3239,14 +3239,14 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
 						   type);
 	  gcc_assert (!(pred->flags & EDGE_ABNORMAL));
 	  gsi_insert_seq_on_edge (pred, stmts);
-	  avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
+	  VEC_replace (pre_expr, avail, pred->dest_idx,
+		       get_or_alloc_expr_for_name (builtexpr));
 	  insertions = true;
 	}
       else if (eprime->kind == CONSTANT)
 	{
 	  /* Constants may not have the right type, fold_convert
-	     should give us back a constant with the right type.
-	  */
+	     should give us back a constant with the right type.  */
 	  tree constant = PRE_EXPR_CONSTANT (eprime);
 	  if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
 	    {
@@ -3278,11 +3278,13 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
 			    }
 			  gsi_insert_seq_on_edge (pred, stmts);
 			}
-		      avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
+		      VEC_replace (pre_expr, avail, pred->dest_idx,
+				   get_or_alloc_expr_for_name (forcedexpr));
 		    }
 		}
 	      else
-		avail[bprime->index] = get_or_alloc_expr_for_constant (builtexpr);
+		VEC_replace (pre_expr, avail, pred->dest_idx,
+			     get_or_alloc_expr_for_constant (builtexpr));
 	    }
 	}
       else if (eprime->kind == NAME)
@@ -3321,7 +3323,8 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
 		    }
 		  gsi_insert_seq_on_edge (pred, stmts);
 		}
-	      avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
+	      VEC_replace (pre_expr, avail, pred->dest_idx,
+			   get_or_alloc_expr_for_name (forcedexpr));
 	    }
 	}
     }
@@ -3344,14 +3347,13 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi)));
   FOR_EACH_EDGE (pred, ei, block->preds)
     {
-      pre_expr ae = avail[pred->src->index];
+      pre_expr ae = VEC_index (pre_expr, avail, pred->dest_idx);
       gcc_assert (get_expr_type (ae) == type
 		  || useless_type_conversion_p (type, get_expr_type (ae)));
       if (ae->kind == CONSTANT)
 	add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
       else
-	add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
-		     UNKNOWN_LOCATION);
+	add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
     }
 
   newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
@@ -3411,15 +3413,18 @@ static bool
 do_regular_insertion (basic_block block, basic_block dom)
 {
   bool new_stuff = false;
-  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
+  VEC (pre_expr, heap) *exprs;
   pre_expr expr;
+  VEC (pre_expr, heap) *avail = NULL;
   int i;
 
+  exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
+  VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds));
+
   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
     {
       if (expr->kind != NAME)
 	{
-	  pre_expr *avail;
 	  unsigned int val;
 	  bool by_some = false;
 	  bool cant_insert = false;
@@ -3442,10 +3447,6 @@ do_regular_insertion (basic_block block, basic_block dom)
 	      continue;
 	    }
 
-	  /* FIXME: This costs N_EXPR*N_BASIC_BLOCKS.  Should use
-	     a less costly data structure for avail (e.g. a VEC
-	     indexed by edge index).  */
-	  avail = XCNEWVEC (pre_expr, last_basic_block);
 	  FOR_EACH_EDGE (pred, ei, block->preds)
 	    {
 	      unsigned int vprime;
@@ -3468,6 +3469,7 @@ do_regular_insertion (basic_block block, basic_block dom)
 		 rest of the results are.  */
 	      if (eprime == NULL)
 		{
+		  VEC_replace (pre_expr, avail, pred->dest_idx, NULL);
 		  cant_insert = true;
 		  break;
 		}
@@ -3478,12 +3480,12 @@ do_regular_insertion (basic_block block, basic_block dom)
 						 vprime, NULL);
 	      if (edoubleprime == NULL)
 		{
-		  avail[bprime->index] = eprime;
+		  VEC_replace (pre_expr, avail, pred->dest_idx, eprime);
 		  all_same = false;
 		}
 	      else
 		{
-		  avail[bprime->index] = edoubleprime;
+		  VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime);
 		  by_some = true;
 		  /* We want to perform insertions to remove a redundancy on
 		     a path in the CFG we want to optimize for speed.  */
@@ -3562,11 +3564,11 @@ do_regular_insertion (basic_block block, basic_block dom)
 		    }
 		}
 	    }
-	  free (avail);
 	}
     }
 
   VEC_free (pre_expr, heap, exprs);
+  VEC_free (pre_expr, heap, avail);
   return new_stuff;
 }
 
@@ -3582,15 +3584,18 @@ static bool
 do_partial_partial_insertion (basic_block block, basic_block dom)
 {
   bool new_stuff = false;
-  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
+  VEC (pre_expr, heap) *exprs;
   pre_expr expr;
+  VEC (pre_expr, heap) *avail = NULL;
   int i;
 
+  exprs = sorted_array_from_bitmap_set (PA_IN (block));
+  VEC_safe_grow (pre_expr, heap, avail, EDGE_COUNT (block->preds));
+
   FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
     {
       if (expr->kind != NAME)
 	{
-	  pre_expr *avail;
 	  unsigned int val;
 	  bool by_all = true;
 	  bool cant_insert = false;
@@ -3605,10 +3610,6 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
 	  if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
 	    continue;
 
-	  /* FIXME: This costs N_EXPR*N_BASIC_BLOCKS.  Should use
-	     a less costly data structure for avail (e.g. a VEC
-	     indexed by edge index).  */
-	  avail = XCNEWVEC (pre_expr, last_basic_block);
 	  FOR_EACH_EDGE (pred, ei, block->preds)
 	    {
 	      unsigned int vprime;
@@ -3633,6 +3634,7 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
 		 rest of the results are.  */
 	      if (eprime == NULL)
 		{
+		  VEC_replace (pre_expr, avail, pred->dest_idx, NULL);
 		  cant_insert = true;
 		  break;
 		}
@@ -3641,13 +3643,12 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
 	      vprime = get_expr_value_id (eprime);
 	      edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
 						 vprime, NULL);
+	      VEC_replace (pre_expr, avail, pred->dest_idx, edoubleprime);
 	      if (edoubleprime == NULL)
 		{
 		  by_all = false;
 		  break;
 		}
-	      else
-		avail[bprime->index] = edoubleprime;
 	    }
 
 	  /* If we can insert it, it's not the same value
@@ -3701,11 +3702,11 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
 		    new_stuff = true;
 		}	   
 	    } 
-	  free (avail);
 	}
     }
 
   VEC_free (pre_expr, heap, exprs);
+  VEC_free (pre_expr, heap, avail);
   return new_stuff;
 }