Re: [PATCH][RFC] Fix PR85180, find_base_term is exponential

[Jeff Law]

On 04/05/2018 06:32 AM, Richard Biener wrote:
> 
> This fixes exponential time spent in find_base_term by extending the
> existing fix of NULL-ifying VALUE locations during their processing
> to keep them NULL-ified during the whole recursion.
> 
> As Jakub figured this has the chance of returning NULL prematurely
> for the case of the plus/minus case rejecting a found base on the
> ground of
> 
> if (base != NULL_RTX
> && ((REG_P (tmp1) && REG_POINTER (tmp1))
>  || known_base_value_p (base)))
>   return base;
> 
> so any VALUE visited during a such rejected base will not be
> visited again (but we'll get a NULL result).
> 
> Quoting him from IRC: still no differences, out of 850mil calls
> 
> for an instrumented version.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
> 
> Alternative (safer in the above regard) variants using a hash-map
> to cache the base for a VALUE are quite a bit slower if not implemented
> in ways that also look dangerous at this point.  See the PR for
> some of those.
> 
> Any comments?  Otherwise we decided to go ahead with this tomorrow.
> 
> Thanks,
> Richard.
> 
> 2018-04-05  Richard Biener  
> 
>   PR middle-end/85180
>   * alias.c (find_base_term): New wrapper around find_base_term
>   unwinding CSELIB_VAL_PTR changes.
>   (find_base_term): Do not restore CSELIB_VAL_PTR during the
>   recursion.
> 
>   * gcc.dg/pr85180.c: New testcase.
Seems reasonable.  I do wonder how much all the complexity in alias.c
buys us these days and whether or not we should look to do some dramatic
simplifications.  The core parts of this code date back to the late 90s
when RTL memory disambiguation was much more important than it is today.

jeff

Re: [PATCH][RFC] Fix PR85180, find_base_term is exponential

[Jakub Jelinek]

On Thu, Apr 05, 2018 at 02:32:08PM +0200, Richard Biener wrote:
> 
> This fixes exponential time spent in find_base_term by extending the
> existing fix of NULL-ifying VALUE locations during their processing
> to keep them NULL-ified during the whole recursion.
> 
> As Jakub figured this has the chance of returning NULL prematurely
> for the case of the plus/minus case rejecting a found base on the
> ground of
> 
> if (base != NULL_RTX
> && ((REG_P (tmp1) && REG_POINTER (tmp1))
>  || known_base_value_p (base)))
>   return base;
> 
> so any VALUE visited during a such rejected base will not be
> visited again (but we'll get a NULL result).
> 
> Quoting him from IRC: still no differences, out of 850mil calls

The final statistics across full simultaneous x86_64-linux and i686-linux
bootstraps + regtests is 5 cases where the patch changed result from
4.6 billion find_base_term toplevel calls, all like:
64 /home/jakub/src/gcc/gcc/testsuite/gcc.target/i386/pr53698.c test2 symbol_ref 
0x7f765b2cc840 0 symbol_ref 0x7f765b2cc858 0
64 /home/jakub/src/gcc/gcc/testsuite/gcc.target/i386/pr53698.c test2 symbol_ref 
0x7f765b2cc870 0 symbol_ref 0x7f765b2cc888 0
64 /home/jakub/src/gcc/gcc/testsuite/gcc.target/i386/pr53698.c test2 symbol_ref 
0x7f765b2cd2e8 0 symbol_ref 0x7f765b2cd300 0
64 /home/jakub/src/gcc/gcc/testsuite/gcc.target/i386/pr53698.c test2 symbol_ref 
0x7f765b2cd378 0 symbol_ref 0x7f765b2cd390 0
64 /home/jakub/src/gcc/gcc/testsuite/gcc.target/i386/pr53698.c test2 symbol_ref 
0x7f765b2cd3a8 0 symbol_ref 0x7f765b2cd3c0 0
but when looking at it under debugger, both result from old find_base_term
and new find_base_term look like:
(gdb) p debug_rtx (res)
(symbol_ref:DI ("foo") [flags 0x40] )
(gdb) p debug_rtx (res2)
(symbol_ref:DI ("foo") [flags 0x40] )
just they don't compare pointer equal.  Because it is -mx32, guess it is
just result of
rtx temp = find_base_value (XEXP (src, 0));

if (temp != 0 && CONSTANT_P (temp))
  temp = convert_memory_address (Pmode, temp);
on SImode SYMBOL_REF and thus not a real difference we'd care about.

Jakub