[PATCH] avoid cselib rtx_equal_for_cselib_1 infinite recursion (PR debug/80025)

[Jeff Law]

On 03/23/2017 02:39 PM, Jakub Jelinek wrote:
> Hi!
>
> On Thu, Mar 23, 2017 at 03:00:04PM +0100, Jakub Jelinek wrote:
>> On Tue, Mar 21, 2017 at 07:43:51PM -0300, Alexandre Oliva wrote:
>>> When two VALUEs are recorded in the cselib equivalence table such that
>>> they are equivalent to each other XORed with the same expression, if
>>> we started a cselib equivalence test between say the odd one and the
>>> even one, we'd end up recursing to compare the even one with the odd
>>> one, and then again, indefinitely.
>>>
>>> This patch cuts off this infinite recursion by recognizing the XOR
>>> special case (it's the only binary commutative operation in which
>>> applying one of the operands of an operation to the result of that
>>> operation brings you back to the other operand) and determining
>>> whether we have an equivalence without recursing down the infinite
>>> path.
>>
>> Is XOR the only special case though?  E.g. PLUS or MINUS with
>> the most negative constant act the same, and I don't see why if unlucky
>> enough with reverse ops etc. you couldn't get something similar through
>> combination thereof, perhaps indirectly through multiple VALUEs.
>>
>> So I think it is safer to just put a cap on the rtx_equal_for_cselib_1
>> recursion depth (should be enough to bump the depth only when walking
>> locs of a VALUE).  I'll test such a patch.
>
> Here is that patch, bootstrapped/regtested on x86_64-linux and i686-linux,
> ok for trunk?  Or shall I turn that 128 into a --param?
>
> 2017-03-23  Jakub Jelinek  <jakub@redhat.com>
>
> 	PR debug/80025
> 	* cselib.h (rtx_equal_for_cselib_1): Add depth argument.
> 	(rtx_equal_for_cselib_p): Pass 0 to it.
> 	* cselib.c (cselib_hasher::equal): Likewise.
> 	(rtx_equal_for_cselib_1): Add depth argument.  If depth
> 	is 128, don't look up VALUE locs and punt.  Increment
> 	depth in recursive calls when walking VALUE locs.
>
> 	* gcc.dg/torture/pr80025.c: New test.
I don't think the depth for this case is worth exposing as a PARAM.


OK for the trunk.

Thanks,
Jeff