Re: [PATCH] Speed up find_loc_in_1pdv (PR debug/41371)

[Richard Guenther <rguenther at suse dot de>]

On Fri, 4 Jun 2010, Jakub Jelinek wrote:

> Hi!
> 
> This is a patch from Alex, I've just bootstrapped/regtested it on
> x86_64-linux and i686-linux.  find_loc_in_1pdv doesn't mark
> the original VALUE as VALUE_RECURSED_INTO, so the recursion is deeper than
> needed and in cases like in the PR41371 testcases that's horribly expensive.
> E.g. on the wine testcase this patch speeds in release checking trunk gcc
> compilation from more than 7 minutes to 56 seconds and similar improvements
> can be seen on the other testcases.
> 
> Ok for trunk?

Ok.  Can you also backport this to the 4.5 branch?

Thanks,
Richard.

> 2010-06-04  Alexandre Oliva  <aoliva@redhat.com>
> 
> 	PR debug/41371
> 	* var-tracking.c (find_loc_in_1pdv): Mark initial value before
> 	recursing.  Check that recursion is bounded.  Rename inner var
> 	to avoid hiding incoming argument.
> 
> --- gcc/var-tracking.c.orig	2010-06-04 05:21:35.000000000 -0300
> +++ gcc/var-tracking.c	2010-06-04 07:05:08.000000000 -0300
> @@ -2486,16 +2486,21 @@ find_loc_in_1pdv (rtx loc, variable var,
>  {
>    location_chain node;
>    enum rtx_code loc_code;
> +  location_chain ret = NULL;
> +  int unmark_self = 0;
> +#ifdef ENABLE_CHECKING
> +  static int mark_count;
> +#endif
>  
>    if (!var)
> -    return NULL;
> +    return ret;
>  
>  #ifdef ENABLE_CHECKING
>    gcc_assert (dv_onepart_p (var->dv));
>  #endif
>  
>    if (!var->n_var_parts)
> -    return NULL;
> +    return ret;
>  
>  #ifdef ENABLE_CHECKING
>    gcc_assert (var->var_part[0].offset == 0);
> @@ -2510,34 +2515,89 @@ find_loc_in_1pdv (rtx loc, variable var,
>  	    continue;
>  	}
>        else if (loc == node->loc)
> -	return node;
> +	{
> +	  ret = node;
> +	  break;
> +	}
>        else if (loc_code != VALUE)
>  	{
>  	  if (rtx_equal_p (loc, node->loc))
> -	    return node;
> +	    {
> +	      ret = node;
> +	      break;
> +	    }
>  	  continue;
>  	}
>        if (!VALUE_RECURSED_INTO (node->loc))
>  	{
>  	  decl_or_value dv = dv_from_value (node->loc);
> -	  variable var = (variable)
> -			 htab_find_with_hash (vars, dv, dv_htab_hash (dv));
> +	  variable rvar = (variable)
> +	    htab_find_with_hash (vars, dv, dv_htab_hash (dv));
>  
> -	  if (var)
> +	  if (rvar)
>  	    {
>  	      location_chain where;
> +
> +	      if (!unmark_self)
> +		{
> +		  if (dv_is_value_p (var->dv)
> +		      && !VALUE_RECURSED_INTO (dv_as_value (var->dv)))
> +		    {
> +		      unmark_self = 1;
> +#ifdef ENABLE_CHECKING
> +		      mark_count++;
> +#endif
> +		      VALUE_RECURSED_INTO (dv_as_value (var->dv)) = true;
> +		    }
> +		  else
> +		    unmark_self = -1;
> +		}
> +
> +#ifdef ENABLE_CHECKING
> +	      mark_count++;
> +	      /* The recursion count is bounded because we're
> +		 searching in a star-canonicalized set, i.e., each
> +		 equivalence set of values is arranged so that the
> +		 canonical value has all locations and equivalent
> +		 values, whereas equivalent values only point back to
> +		 the canonical.  So, if we start at the canonical
> +		 value, we'll recurse at most into each sibling, so
> +		 the recurse limit will be 2.  If we start at a
> +		 non-canonical value, we'll recurse into the
> +		 canonical, and from there to other siblings, so
> +		 recurse limit will be 3.  If we start at a one-part
> +		 variable, we add one level of recursion, but we don't
> +		 count it.  */
> +	      gcc_assert (mark_count <= 3);
> +#endif
>  	      VALUE_RECURSED_INTO (node->loc) = true;
> -	      if ((where = find_loc_in_1pdv (loc, var, vars)))
> +	      if ((where = find_loc_in_1pdv (loc, rvar, vars)))
>  		{
> +#ifdef ENABLE_CHECKING
> +		  mark_count--;
> +#endif
>  		  VALUE_RECURSED_INTO (node->loc) = false;
> -		  return where;
> +		  ret = where;
> +		  break;
>  		}
>  	      VALUE_RECURSED_INTO (node->loc) = false;
> +#ifdef ENABLE_CHECKING
> +	      mark_count--;
> +#endif
>  	    }
>  	}
>      }
>  
> -  return NULL;
> +  if (unmark_self > 0)
> +    {
> +      VALUE_RECURSED_INTO (dv_as_value (var->dv)) = false;
> +#ifdef ENABLE_CHECKING
> +      mark_count--;
> +      gcc_assert (mark_count == 0);
> +#endif
> +    }
> +
> +  return ret;
>  }
>  
>  /* Hash table iteration argument passed to variable_merge.  */
> 
> 	Jakub
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex