diff mbox

[PR80025] avoid cselib rtx_equal infinite recursion on XOR

Message ID orwpbiuu6w.fsf@lxoliva.fsfla.org
State New
Headers show

Commit Message

Alexandre Oliva March 21, 2017, 10:43 p.m. UTC 
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

Comments

Jakub Jelinek March 23, 2017, 2 p.m. UTC | #1 
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
diff mbox

Patch

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);
+}