Patchwork Limit SLSR increment vector size to avoid quadratic behavior

login
register
mail settings
Submitter William J. Schmidt
Date May 7, 2013, 1:22 p.m.
Message ID <1367932960.4938.21.camel@oc8801110288.ibm.com>
Download mbox | patch
Permalink /patch/242199/
State New
Headers show

Comments

William J. Schmidt - May 7, 2013, 1:22 p.m.
This handles the unlikely case where there are many different increments
associated with a group of related SLSR candidates, which could result
in poor performance when doing linear searches of the increment vector.
The size of the increment vector is limited to a reasonable constant,
and increments that do not appear in the increment vector are not
processed.

Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new
regressions.  Ok for trunk?

Thanks,
Bill


2013-05-06  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	* gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant.
	(incr_vec_index): Return -1 if increment not found.
	(create_add_on_incoming_edge): Assert if increment not found.
	(record_increment): Limit number of increments recorded.
	(all_phi_incrs_profitable): Return false if an increment not found.
	(replace_profitable_candidates): Don't process increments that were
	not recorded.
	(analyze_candidates_and_replace): Limit size of incr_vec.
Richard Guenther - May 7, 2013, 1:42 p.m.
On Tue, 7 May 2013, Bill Schmidt wrote:

> This handles the unlikely case where there are many different increments
> associated with a group of related SLSR candidates, which could result
> in poor performance when doing linear searches of the increment vector.
> The size of the increment vector is limited to a reasonable constant,
> and increments that do not appear in the increment vector are not
> processed.
> 
> Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new
> regressions.  Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> Bill
> 
> 
> 2013-05-06  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
> 
> 	* gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant.
> 	(incr_vec_index): Return -1 if increment not found.
> 	(create_add_on_incoming_edge): Assert if increment not found.
> 	(record_increment): Limit number of increments recorded.
> 	(all_phi_incrs_profitable): Return false if an increment not found.
> 	(replace_profitable_candidates): Don't process increments that were
> 	not recorded.
> 	(analyze_candidates_and_replace): Limit size of incr_vec.
> 
> 
> Index: gcc/gimple-ssa-strength-reduction.c
> ===================================================================
> --- gcc/gimple-ssa-strength-reduction.c	(revision 198680)
> +++ gcc/gimple-ssa-strength-reduction.c	(working copy)
> @@ -366,9 +366,11 @@ static struct obstack chain_obstack;
>  
>  /* An array INCR_VEC of incr_infos is used during analysis of related
>     candidates having an SSA name for a stride.  INCR_VEC_LEN describes
> -   its current length.  */
> +   its current length.  MAX_INCR_VEC_LEN is used to avoid costly
> +   pathological cases. */
>  static incr_info_t incr_vec;
>  static unsigned incr_vec_len;
> +const int MAX_INCR_VEC_LEN = 16;
>  
>  /* For a chain of candidates with unknown stride, indicates whether or not
>     we must generate pointer arithmetic when replacing statements.  */
> @@ -1960,9 +1962,11 @@ replace_unconditional_candidate (slsr_cand_t c)
>    replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump);
>  }
>  
> -/* Return the index in the increment vector of the given INCREMENT.  */
> +/* Return the index in the increment vector of the given INCREMENT,
> +   or -1 if not found.  The latter can occur if more than
> +   MAX_INCR_VEC_LEN increments have been found.  */
>  
> -static inline unsigned
> +static inline int
>  incr_vec_index (double_int increment)
>  {
>    unsigned i;
> @@ -1970,8 +1974,10 @@ incr_vec_index (double_int increment)
>    for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++)
>      ;
>  
> -  gcc_assert (i < incr_vec_len);
> -  return i;
> +  if (i < incr_vec_len)
> +    return i;
> +  else
> +    return -1;
>  }
>  
>  /* Create a new statement along edge E to add BASIS_NAME to the product
> @@ -2015,9 +2021,10 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b
>      }
>    else
>      {
> -      unsigned i;
> +      int i;
>        bool negate_incr = (!address_arithmetic_p && increment.is_negative ());
>        i = incr_vec_index (negate_incr ? -increment : increment);
> +      gcc_assert (i >= 0);
>  
>        if (incr_vec[i].initializer)
>  	{
> @@ -2323,7 +2330,7 @@ record_increment (slsr_cand_t c, double_int increm
>  	}
>      }
>  
> -  if (!found)
> +  if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1)
>      {
>        /* The first time we see an increment, create the entry for it.
>  	 If this is the root candidate which doesn't have a basis, set
> @@ -3025,7 +3032,7 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph
>  	    }
>  	  else
>  	    {
> -	      unsigned j;
> +	      int j;
>  	      slsr_cand_t arg_cand = base_cand_from_table (arg);
>  	      double_int increment = arg_cand->index - basis->index;
>  
> @@ -3041,14 +3048,19 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph
>  		  print_gimple_stmt (dump_file, phi, 0, 0);
>  		  fputs ("    increment: ", dump_file);
>  		  dump_double_int (dump_file, increment, false);
> -		  fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
> -		  if (profitable_increment_p (j))
> -		    fputs ("  Replacing...\n", dump_file);
> -		  else
> -		    fputs ("  Not replaced.\n", dump_file);
> +		  if (j < 0)
> +		    fprintf (dump_file,
> +			     "\n  Not replaced; incr_vec overflow.\n");
> +		  else {
> +		    fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
> +		    if (profitable_increment_p (j))
> +		      fputs ("  Replacing...\n", dump_file);
> +		    else
> +		      fputs ("  Not replaced.\n", dump_file);
> +		  }
>  		}
>  
> -	      if (!profitable_increment_p (j))
> +	      if (j < 0 || !profitable_increment_p (j))
>  		return false;
>  	    }
>  	}
> @@ -3268,13 +3280,14 @@ replace_profitable_candidates (slsr_cand_t c)
>      {
>        double_int increment = cand_abs_increment (c);
>        enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
> -      unsigned i;
> +      int i;
>  
>        i = incr_vec_index (increment);
>  
>        /* Only process profitable increments.  Nothing useful can be done
>  	 to a cast or copy.  */
> -      if (profitable_increment_p (i) 
> +      if (i >= 0
> +	  && profitable_increment_p (i) 
>  	  && orig_code != MODIFY_EXPR
>  	  && orig_code != NOP_EXPR)
>  	{
> @@ -3378,6 +3391,8 @@ analyze_candidates_and_replace (void)
>  	  length = count_candidates (c);
>  	  if (!length)
>  	    continue;
> +	  if (length > MAX_INCR_VEC_LEN)
> +	    length = MAX_INCR_VEC_LEN;
>  
>  	  /* Construct an array of increments for this candidate chain.  */
>  	  incr_vec = XNEWVEC (incr_info, length);
> 
> 
>
Jeff Law - May 7, 2013, 4:21 p.m.
On 05/07/2013 07:22 AM, Bill Schmidt wrote:
> This handles the unlikely case where there are many different increments
> associated with a group of related SLSR candidates, which could result
> in poor performance when doing linear searches of the increment vector.
> The size of the increment vector is limited to a reasonable constant,
> and increments that do not appear in the increment vector are not
> processed.
>
> Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new
> regressions.  Ok for trunk?
>
> Thanks,
> Bill
>
>
> 2013-05-06  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
>
> 	* gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant.
> 	(incr_vec_index): Return -1 if increment not found.
> 	(create_add_on_incoming_edge): Assert if increment not found.
> 	(record_increment): Limit number of increments recorded.
> 	(all_phi_incrs_profitable): Return false if an increment not found.
> 	(replace_profitable_candidates): Don't process increments that were
> 	not recorded.
> 	(analyze_candidates_and_replace): Limit size of incr_vec.
BTW, I'd be interested to know if anyone has poked at the SH port to see 
if SLSR eliminates the need for reload_cse_move2add?

Who does SH stuff these days?

jeff

Patch

Index: gcc/gimple-ssa-strength-reduction.c
===================================================================
--- gcc/gimple-ssa-strength-reduction.c	(revision 198680)
+++ gcc/gimple-ssa-strength-reduction.c	(working copy)
@@ -366,9 +366,11 @@  static struct obstack chain_obstack;
 
 /* An array INCR_VEC of incr_infos is used during analysis of related
    candidates having an SSA name for a stride.  INCR_VEC_LEN describes
-   its current length.  */
+   its current length.  MAX_INCR_VEC_LEN is used to avoid costly
+   pathological cases. */
 static incr_info_t incr_vec;
 static unsigned incr_vec_len;
+const int MAX_INCR_VEC_LEN = 16;
 
 /* For a chain of candidates with unknown stride, indicates whether or not
    we must generate pointer arithmetic when replacing statements.  */
@@ -1960,9 +1962,11 @@  replace_unconditional_candidate (slsr_cand_t c)
   replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump);
 }
 
-/* Return the index in the increment vector of the given INCREMENT.  */
+/* Return the index in the increment vector of the given INCREMENT,
+   or -1 if not found.  The latter can occur if more than
+   MAX_INCR_VEC_LEN increments have been found.  */
 
-static inline unsigned
+static inline int
 incr_vec_index (double_int increment)
 {
   unsigned i;
@@ -1970,8 +1974,10 @@  incr_vec_index (double_int increment)
   for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++)
     ;
 
-  gcc_assert (i < incr_vec_len);
-  return i;
+  if (i < incr_vec_len)
+    return i;
+  else
+    return -1;
 }
 
 /* Create a new statement along edge E to add BASIS_NAME to the product
@@ -2015,9 +2021,10 @@  create_add_on_incoming_edge (slsr_cand_t c, tree b
     }
   else
     {
-      unsigned i;
+      int i;
       bool negate_incr = (!address_arithmetic_p && increment.is_negative ());
       i = incr_vec_index (negate_incr ? -increment : increment);
+      gcc_assert (i >= 0);
 
       if (incr_vec[i].initializer)
 	{
@@ -2323,7 +2330,7 @@  record_increment (slsr_cand_t c, double_int increm
 	}
     }
 
-  if (!found)
+  if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1)
     {
       /* The first time we see an increment, create the entry for it.
 	 If this is the root candidate which doesn't have a basis, set
@@ -3025,7 +3032,7 @@  all_phi_incrs_profitable (slsr_cand_t c, gimple ph
 	    }
 	  else
 	    {
-	      unsigned j;
+	      int j;
 	      slsr_cand_t arg_cand = base_cand_from_table (arg);
 	      double_int increment = arg_cand->index - basis->index;
 
@@ -3041,14 +3048,19 @@  all_phi_incrs_profitable (slsr_cand_t c, gimple ph
 		  print_gimple_stmt (dump_file, phi, 0, 0);
 		  fputs ("    increment: ", dump_file);
 		  dump_double_int (dump_file, increment, false);
-		  fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
-		  if (profitable_increment_p (j))
-		    fputs ("  Replacing...\n", dump_file);
-		  else
-		    fputs ("  Not replaced.\n", dump_file);
+		  if (j < 0)
+		    fprintf (dump_file,
+			     "\n  Not replaced; incr_vec overflow.\n");
+		  else {
+		    fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
+		    if (profitable_increment_p (j))
+		      fputs ("  Replacing...\n", dump_file);
+		    else
+		      fputs ("  Not replaced.\n", dump_file);
+		  }
 		}
 
-	      if (!profitable_increment_p (j))
+	      if (j < 0 || !profitable_increment_p (j))
 		return false;
 	    }
 	}
@@ -3268,13 +3280,14 @@  replace_profitable_candidates (slsr_cand_t c)
     {
       double_int increment = cand_abs_increment (c);
       enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
-      unsigned i;
+      int i;
 
       i = incr_vec_index (increment);
 
       /* Only process profitable increments.  Nothing useful can be done
 	 to a cast or copy.  */
-      if (profitable_increment_p (i) 
+      if (i >= 0
+	  && profitable_increment_p (i) 
 	  && orig_code != MODIFY_EXPR
 	  && orig_code != NOP_EXPR)
 	{
@@ -3378,6 +3391,8 @@  analyze_candidates_and_replace (void)
 	  length = count_candidates (c);
 	  if (!length)
 	    continue;
+	  if (length > MAX_INCR_VEC_LEN)
+	    length = MAX_INCR_VEC_LEN;
 
 	  /* Construct an array of increments for this candidate chain.  */
 	  incr_vec = XNEWVEC (incr_info, length);