[PR80025] avoid cselib rtx_equal infinite recursion on XOR

[PR80025] avoid cselib rtx_equal infinite recursion on XOR

[Alexandre Oliva]

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.


I know Bernd and Jakub may look further into this issue, trying to stop
the cycle in cselib structures from forming to begin with, but I
unexpectedly managed to complete a test cycle of this before taking off
for a one-week trip (anyone else going to be at LibrePlanet?), so I'm
posting it for consideration, and so that there's at least a workaround
on the archives.

FWIW, I do believe the patch is the right fix, and that the cycle in the
data structures is not something to be avoided, since it reflects the
equivalences in the code.  However, if there's a general agreement that
the presence of the cycle is not useful (or even that it's harmful), and
someone finds a good way to avoid it, I won't stand in the way ;-)

Regstrapped on x86_64-linux-gnu and i686-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	* cselib.c (rtx_equal_for_cselib_1): Avoid infinite recursion
        on XOR.

for  gcc/testsuite/ChangeLog

	* gcc.dg/torture/pr80025.c: New.
---
 gcc/cselib.c                           |   24 ++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/torture/pr80025.c |   26 ++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr80025.c

diff --git a/gcc/cselib.c b/gcc/cselib.c
index a621f0d..83c2e45 100644
--- a/gcc/cselib.c
+++ b/gcc/cselib.c
@@ -955,6 +955,30 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode)
 	 using this MEM's mode.  */
       return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x));
 
+    case XOR:
+      /* Catch cases in which we might recurse indefinitely because
+	 two XORs with the same value cancel out, yielding the
+	 original value.  In some circumstances, we might find
+	 ourselves attempting to expand one operand of both XORs and
+	 comparing again, which is just another way of commuting the
+	 compare, and if we were to then expand again, we'd be back at
+	 square one.  It's safe to compare for equality here, because
+	 if this is the case we're interested in, we'll have taken the
+	 rtxes from equivalence lists.  Besides, we couldn't use
+	 rtx_equal_for_cselib_1 instead: that might just turn a case
+	 in which the present call would yield an equality into an
+	 infinite recursion at this point!  */
+      if (XEXP (x, 0) == y)
+	return rtx_equal_for_cselib_1 (XEXP (x, 1), const0_rtx, GET_MODE (x));
+      else if (XEXP (x, 1) == y)
+	return rtx_equal_for_cselib_1 (XEXP (x, 0), const0_rtx, GET_MODE (x));
+      else if (XEXP (y, 0) == x)
+	return rtx_equal_for_cselib_1 (XEXP (y, 1), const0_rtx, GET_MODE (x));
+      else if (XEXP (y, 1) == x)
+	return rtx_equal_for_cselib_1 (XEXP (y, 0), const0_rtx, GET_MODE (x));
+      else
+	break;
+
     default:
       break;
     }
diff --git a/gcc/testsuite/gcc.dg/torture/pr80025.c b/gcc/testsuite/gcc.dg/torture/pr80025.c
new file mode 100644
index 0000000..e6a3b04d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr80025.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-g -w -ftracer" } */
+
+int kq;
+long int cs, l3;
+
+long int
+gn (void)
+{
+}
+
+void
+yc (int un, short int z6, unsigned short int il)
+{
+  (void)un;
+  (void)z6;
+  (void)il;
+}
+
+int
+w6 (void)
+{
+  kq -= cs;
+  cs = !gn ();
+  yc (cs ^= (l3 ^ 1) ? (l3 ^ 1) : gn (), &yc, kq);
+}

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist|Red Hat Brasil GNU Toolchain Engineer

Re: [PR80025] avoid cselib rtx_equal infinite recursion on XOR

[Jakub Jelinek]

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.

	Jakub

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

[Jakub Jelinek]

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.

--- gcc/cselib.h.jj	2017-01-01 12:45:37.000000000 +0100
+++ gcc/cselib.h	2017-03-23 14:06:35.348504435 +0100
@@ -82,7 +82,7 @@ extern void cselib_finish (void);
 extern void cselib_process_insn (rtx_insn *);
 extern bool fp_setter_insn (rtx_insn *);
 extern machine_mode cselib_reg_set_mode (const_rtx);
-extern int rtx_equal_for_cselib_1 (rtx, rtx, machine_mode);
+extern int rtx_equal_for_cselib_1 (rtx, rtx, machine_mode, int);
 extern int references_value_p (const_rtx, int);
 extern rtx cselib_expand_value_rtx (rtx, bitmap, int);
 typedef rtx (*cselib_expand_callback)(rtx, bitmap, int, void *);
@@ -134,7 +134,7 @@ rtx_equal_for_cselib_p (rtx x, rtx y)
   if (x == y)
     return 1;
 
-  return rtx_equal_for_cselib_1 (x, y, VOIDmode);
+  return rtx_equal_for_cselib_1 (x, y, VOIDmode, 0);
 }
 
 #endif /* GCC_CSELIB_H */
--- gcc/cselib.c.jj	2017-01-01 12:45:39.000000000 +0100
+++ gcc/cselib.c	2017-03-23 14:38:50.238487353 +0100
@@ -125,7 +125,7 @@ cselib_hasher::equal (const cselib_val *
   /* We don't guarantee that distinct rtx's have different hash values,
      so we need to do a comparison.  */
   for (l = v->locs; l; l = l->next)
-    if (rtx_equal_for_cselib_1 (l->loc, x, memmode))
+    if (rtx_equal_for_cselib_1 (l->loc, x, memmode, 0))
       {
 	promote_debug_loc (l);
 	return true;
@@ -834,7 +834,7 @@ autoinc_split (rtx x, rtx *off, machine_
    addresses, MEMMODE should be VOIDmode.  */
 
 int
-rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode)
+rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth)
 {
   enum rtx_code code;
   const char *fmt;
@@ -867,6 +867,9 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
       if (GET_CODE (y) == VALUE)
 	return e == canonical_cselib_val (CSELIB_VAL_PTR (y));
 
+      if (depth == 128)
+	return 0;
+
       for (l = e->locs; l; l = l->next)
 	{
 	  rtx t = l->loc;
@@ -876,7 +879,7 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
 	     list.  */
 	  if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
 	    continue;
-	  else if (rtx_equal_for_cselib_1 (t, y, memmode))
+	  else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1))
 	    return 1;
 	}
 
@@ -887,13 +890,16 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
       cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y));
       struct elt_loc_list *l;
 
+      if (depth == 128)
+	return 0;
+
       for (l = e->locs; l; l = l->next)
 	{
 	  rtx t = l->loc;
 
 	  if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
 	    continue;
-	  else if (rtx_equal_for_cselib_1 (x, t, memmode))
+	  else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1))
 	    return 1;
 	}
 
@@ -914,12 +920,12 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
       if (!xoff != !yoff)
 	return 0;
 
-      if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode))
+      if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth))
 	return 0;
 
       /* Don't recurse if nothing changed.  */
       if (x != xorig || y != yorig)
-	return rtx_equal_for_cselib_1 (x, y, memmode);
+	return rtx_equal_for_cselib_1 (x, y, memmode, depth);
 
       return 0;
     }
@@ -953,7 +959,8 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
     case MEM:
       /* We have to compare any autoinc operations in the addresses
 	 using this MEM's mode.  */
-      return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x));
+      return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x),
+				     depth);
 
     default:
       break;
@@ -988,17 +995,20 @@ rtx_equal_for_cselib_1 (rtx x, rtx y, ma
 	  /* And the corresponding elements must match.  */
 	  for (j = 0; j < XVECLEN (x, i); j++)
 	    if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j),
-					  XVECEXP (y, i, j), memmode))
+					  XVECEXP (y, i, j), memmode, depth))
 	      return 0;
 	  break;
 
 	case 'e':
 	  if (i == 1
 	      && targetm.commutative_p (x, UNKNOWN)
-	      && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode)
-	      && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode))
+	      && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode,
+					 depth)
+	      && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode,
+					 depth))
 	    return 1;
-	  if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode))
+	  if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode,
+					depth))
 	    return 0;
 	  break;
 
--- gcc/testsuite/gcc.dg/torture/pr80025.c.jj	2017-03-23 14:44:34.801024681 +0100
+++ gcc/testsuite/gcc.dg/torture/pr80025.c	2017-03-23 14:43:54.000000000 +0100
@@ -0,0 +1,24 @@
+/* PR debug/80025 */
+/* { dg-do compile } */
+/* { dg-options "-g -ftracer -w" } */
+
+int a;
+long int b, c;
+
+long int
+foo (void)
+{
+}
+
+void
+bar (int x, short int y, unsigned short int z)
+{
+}
+
+int
+baz (void)
+{
+  a -= b;
+  b = !foo ();
+  bar (b ^= (c ^ 1) ? (c ^ 1) : foo (), (__INTPTR_TYPE__) &bar, a);
+}


	Jakub

Re: [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