[PR64817-related 3/3] simplify xor of (and or ior) of xor

[Alexandre Oliva <aoliva at redhat dot com>]

PR64817's testcase creates a long chain of XOR of AND of XOR of AND of
that our rtl simplifiers can't simplify, although they are simplifyable.

combine manages to simplify the generated insns that perform the
computation represented by such chains, but simplify-rtx doesn't.
That's because combine notices that, after the first and with a
constant, some bits are necessarily zero, and so it can simplify
subsequent redundant insns.

simplify-rtx doesn't do that, though.  I suppose it could try to compute
the nonzero bits of its operands, but doing so would likely lead to
exponential behavior on the depth of the expression.

We can still simplify the expressions to a great extent, though: for
each sequence of xor of and of xor of whatever, with constant second
operands for each of the 3 operations, we can get rid of the innermost
xor by tweaking the operands of the outermost one.  We can also do that
if the intervening operation is an ior rather than an and, though with a
slightly different adjustment for the second operand of the outermost
xor.

With this patch, the huge rtl debug location expressions in the
testcases for pr64817 simplify just as well as combine manages to
simplify them.

I'm a bit surprised the gimple layer does not even attempt to simplify
them, but I didn't try to tackle that, since I was not even sure this
was a useful optimization.  After all, how often do we see xor of and of
xor of and of xor of... in the wild, rather than in pathological
testcases? :-)  But hey, at least the rtl simplification is cheap, so
why not?

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

for  gcc/ChangeLog

	* simplify-rtx.c (simplify_binary_operation_1): Simplify one
	of two XORs that have an intervening AND or IOR.
---
 gcc/simplify-rtx.c |   33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c
index bea9ec3..04452c6 100644
--- a/gcc/simplify-rtx.c
+++ b/gcc/simplify-rtx.c
@@ -2708,6 +2708,39 @@ simplify_binary_operation_1 (enum rtx_code code, machine_mode mode,
 							XEXP (op0, 1), mode),
 				    op1);
 
+      /* Given (xor (ior (xor A B) C) D), where B, C and D are
+	 constants, simplify to (xor (ior A C) (B&~C)^D), canceling
+	 out bits inverted twice and not set by C.  Similarly, given
+	 (xor (and (xor A B) C) D), simplify without inverting C in
+	 the xor operand: (xor (and A C) (B&C)^D).
+      */
+      else if ((GET_CODE (op0) == IOR || GET_CODE (op0) == AND)
+	       && GET_CODE (XEXP (op0, 0)) == XOR
+	       && CONST_INT_P (op1)
+	       && CONST_INT_P (XEXP (op0, 1))
+	       && CONST_INT_P (XEXP (XEXP (op0, 0), 1)))
+	{
+	  enum rtx_code op = GET_CODE (op0);
+	  rtx a = XEXP (XEXP (op0, 0), 0);
+	  rtx b = XEXP (XEXP (op0, 0), 1);
+	  rtx c = XEXP (op0, 1);
+	  rtx d = op1;
+	  HOST_WIDE_INT bval = INTVAL (b);
+	  HOST_WIDE_INT cval = INTVAL (c);
+	  HOST_WIDE_INT dval = INTVAL (d);
+	  HOST_WIDE_INT xcval;
+
+	  if (op == IOR)
+	    xcval = cval;
+	  else
+	    xcval = ~cval;
+
+	  return simplify_gen_binary (XOR, mode,
+				      simplify_gen_binary (op, mode, a, c),
+				      gen_int_mode ((bval & xcval) ^ dval,
+						    mode));
+	}
+
       /* Given (xor (and A B) C), using P^Q == (~P&Q) | (~Q&P),
 	 we can transform like this:
             (A&B)^C == ~(A&B)&C | ~C&(A&B)


-- 
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