This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][RFC] Fix PR85180, find_base_term is exponential
- From: Jeff Law <law at redhat dot com>
- To: Richard Biener <rguenther at suse dot de>, gcc-patches at gcc dot gnu dot org
- Cc: Jakub Jelinek <jakub at redhat dot com>
- Date: Mon, 9 Apr 2018 16:33:33 -0600
- Subject: Re: [PATCH][RFC] Fix PR85180, find_base_term is exponential
- Autocrypt: addr=law at redhat dot com; prefer-encrypt=mutual; keydata= xsBNBFkbIO8BCACVIqDhDVh9ur8C+zNV1J/cXfwvVDAUcphDEFl4jyHqZORK4Pd3Db8oWqLm Q8lOCr/VOS7lrCtdpVMQkLGOGA16oJ8g7hzhnojpjY09UjsoUiG7oKacuxj8skfp6SIx93Zl +iNYPRa4S+za6nY8qiVjyUuiyX04ZPZMrKp2c2sGi+HnBKUZXGhrz/Jdzdox3tjajWZnObyy nhEN6hn9L3KawTtGPE/R6A/1RhHTD9FQmIWIeucpaY5c6GNKXTFpj2VYx57LY5hve1R5vhrJ IZcgwZAiOtmik5lVi96glY5h6bugRwpexjhwORTLPBCkwiYotSxX99mWd6EHL576i5CNABEB AAHNGUplZmYgTGF3IDxsYXdAcmVkaGF0LmNvbT7CwI4EEwEIADgWIQR+niGjtnP5P/8PpRq8 fP682pgzWwUCWRsg7wIbAwULCQgHAgYVCAkKCwIEFgIDAQIeAQIXgAAKCRC8fP682pgzW5QG B/9VATJmx5235RB+8jiDYGXQf3vd9gBfPy/l1tsaK400eFAevDzfGvKmeCKe+uGnlrH3vyT8 rg9zqH+s5a1Y+lDXPOpJAFmmzbOLU4FW4ucbawmtYvBL65PqpQneCTYnC802/OAcxjm/Onem HlgeK6WicNsBTPwYN/0araDFUejyYBIFi9CNqqflwk5Z3brKbQ9bAYIkysVLC/c3njKPmM0c WPFHG91ubLbWCHwTIK0+mAL714eTD74dXzOjO2ZDBPLGlFN/kO3+YjaO6UOD2O8acvAMCivT kWLr7JwRgLIQDN2DkhQDd3LTPqQE/yOcMcXBTO+fxm8KG0iKQBqWMyGJzsBNBFkbIO8BCACy qbOsv7XegSeea8XORt5zMaBVWKoSyhmmcCmlxZFS2cuYOBt79MO13lZE2DlO3Lv5IKikj/D4 ketGVO4+h5psEMH5Yz5P8bx0TmgwbK1GxPZrzeXozUFJDvvCDbIlT0v0pwUXuK3hg8Ieo2h5 uTed/cn1OjySXW5BqLxN0cyr5hL+J6dcsHvKLT/N3nTgCQhoJXK2MrEMhAGgF3jKpMn3CoS4 i/ZbNI2MQR6LWHwdZ95f0fI8NzHSfVzeLtzCKQec7nr9fgd6Ylk1ZpGWQUPlQmKjzYgeCeTK NO04cwt20WIrQWeWiZFPA0U86NDBdSBrYp4kG3dfIXE+wSSvE7qPABEBAAHCwHYEGAEIACAW IQR+niGjtnP5P/8PpRq8fP682pgzWwUCWRsg7wIbDAAKCRC8fP682pgzW3REB/9cT7iKRPg/ OK9bpLlllIEDM90IaKC79DQrv+fRudOR78cdV4XUwPSFnyHUsP3VJ4lDy5FhiKCwGie0BK53 EsxgMrLy1L8hboFdTE4Vi0xzCheMaMVp4hATDU29k1cuxu1VPpCa8E3mYeHjNV7ip0HN5L4D rfs8lRPJE/oM1vGs9DgQFZrCPPNRNGKC97BH+DHccesEJr7tSsQrkPkt0z/FTKr5wIM02vSx OJjgmcVbGB7dc2j/Sx8loXmuKnuKtM35668kUG8jeJvSQk3o/VHpD27bhl0rR68R2jN6G6kQ egMVb6dPu1Ius8rBE5rFw88J4JEb5q4hMNClWWUFHIdP
- Openpgp: preference=signencrypt
- References: <alpine.LSU.2.20.1804051427340.18265@zhemvz.fhfr.qr>
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 <rguenther@suse.de>
>
> 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