Re: PR rtl-optimization/28071 (regmove quadratic behaviour)

[Roger Sayle <roger at eyesopen dot com>]

Hi Jan,

On Tue, 25 Jul 2006, Jan Hubicka wrote:
> 2006-07-25  Jan Hubicka  <jh@suse.cz>
>
> 	PR rtl-optimization/28071
> 	* regmove.c (reg_is_remote_constant_p): Avoid quadratic behaviour.
> 	(reg_set_in_bb, max_reg_computed): New static variables.
> 	(regmove_optimize): Free the new array.
> 	(fixup_match_1): Update call of reg_is_remote_constant_p.

This is OK for mainline with a few changes...

> + static basic_block *reg_set_in_bb;
> + static unsigned int max_reg_computed;

These new global variables should probably have a comment above them
explaining what they're for.


>         if (s != 0
> ! 	  && REG_P (SET_DEST (s)) && REG_N_SETS (REGNO (SET_DEST (s))) == 1
> ! 	  && find_reg_note (p, REG_EQUAL, NULL_RTX))

In the original everything was nicely formatted with one term of the
conjunction per line as preferred by GCC's coding style, and you've
changed this to instead put multiple conditions on a single source line
(in two places).

The new structure of reg_is_remote_constant_p is also a bit odd.
There's absolutely no need for it to be written in a recursive form
like:

int foo(int x)
{
  if (cached)
    return cached[x];
  calculate_cached();
  return foo(x);
}

instead it's much simpler to express what you want with:

int foo(int x)
{
  if (!cached)
    calculate_cached();
  return cached[x];
}


A function that recursively invokes itself with unmodified arguments
is the sort of thing a compiler should consider warning about, as it
normally indicates a lack of progress towards a termination invariant.
Making functions recursive just for the hell of it only make cgraph's
life more difficult :-)

Finally, now might also be a good time to change the return type of
reg_is_remote_constant_p to be bool instead of int.



The timing improvements are impressive!  But as with all changes that
throttle optimizations, please keep an eye on the SPEC testers just
in any of the benchmarks are adversely affected by this change.  I'd
doubt it, given that combine.c has no changes, but just in case.

Thanks for fixing this.


Roger
--