diff mbox

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

Message ID orvbjip56w.fsf@livre.home
State New
Headers show

Commit Message

Alexandre Oliva Feb. 4, 2015, 6:21 a.m. UTC 
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(+)

Comments

Jakub Jelinek Feb. 4, 2015, 8:35 a.m. UTC | #1 
On Wed, Feb 04, 2015 at 04:21:43AM -0200, Alexandre Oliva wrote:
> 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?

I think we should teach at least VRP to simplify debug stmts similarly how
it simplifies normal comparisons etc. using value ranges, but that would be
stage1 material.

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

Ok, thanks.

	Jakub
Richard Biener Feb. 4, 2015, 8:54 a.m. UTC | #2 
On February 4, 2015 9:35:13 AM CET, Jakub Jelinek <jakub@redhat.com> wrote:
>On Wed, Feb 04, 2015 at 04:21:43AM -0200, Alexandre Oliva wrote:
>> 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?
>
>I think we should teach at least VRP to simplify debug stmts similarly
>how
>it simplifies normal comparisons etc. using value ranges, but that
>would be
>stage1 material.

So I suppose this is only about debug exprs and we optimize regular gimple well?  Otherwise adding some patterns to match.PD could help.

Richard.

>> 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.
>
>Ok, thanks.
>
>	Jakub
Jakub Jelinek Feb. 4, 2015, 9:15 a.m. UTC | #3 
On Wed, Feb 04, 2015 at 09:54:53AM +0100, Richard Biener wrote:
> On February 4, 2015 9:35:13 AM CET, Jakub Jelinek <jakub@redhat.com> wrote:
> >On Wed, Feb 04, 2015 at 04:21:43AM -0200, Alexandre Oliva wrote:
> >> 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?
> >
> >I think we should teach at least VRP to simplify debug stmts similarly
> >how
> >it simplifies normal comparisons etc. using value ranges, but that
> >would be
> >stage1 material.
> 
> So I suppose this is only about debug exprs and we optimize regular gimple
> well?  Otherwise adding some patterns to match.PD could help.

Sure.  For e.g. VRP I meant that simplify_stmt_using_ranges could also
attempt to simplify (some) debug_bind stmts, similarly how it optimizes
normal stmts.

	Jakub
Richard Biener Feb. 4, 2015, 9:54 a.m. UTC | #4 
On February 4, 2015 10:15:30 AM CET, Jakub Jelinek <jakub@redhat.com> wrote:
>On Wed, Feb 04, 2015 at 09:54:53AM +0100, Richard Biener wrote:
>> On February 4, 2015 9:35:13 AM CET, Jakub Jelinek <jakub@redhat.com>
>wrote:
>> >On Wed, Feb 04, 2015 at 04:21:43AM -0200, Alexandre Oliva wrote:
>> >> 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?
>> >
>> >I think we should teach at least VRP to simplify debug stmts
>similarly
>> >how
>> >it simplifies normal comparisons etc. using value ranges, but that
>> >would be
>> >stage1 material.
>> 
>> So I suppose this is only about debug exprs and we optimize regular
>gimple
>> well?  Otherwise adding some patterns to match.PD could help.
>
>Sure.  For e.g. VRP I meant that simplify_stmt_using_ranges could also
>attempt to simplify (some) debug_bind stmts, similarly how it optimizes
>normal stmts.

Sure.  Of course it's bad that debug stmts use Generic...  General fold-stmt could do some of the work.  Also that debug temps have no use-def chains doesn't help too much.

Richard.

>	Jakub
Jakub Jelinek Feb. 4, 2015, 10 a.m. UTC | #5 
On Wed, Feb 04, 2015 at 10:54:54AM +0100, Richard Biener wrote:
> Sure.  Of course it's bad that debug stmts use Generic...  General
> fold-stmt could do some of the work.  Also that debug temps have no
> use-def chains doesn't help too much.

Well, at least right now I believe debug temps work more like non-SSA
variables rather than SSA_NAMEs, the same debug temp can be bound to
different values at different points.  At least e.g. loop unrolling
certainly doesn't create new debug temps, but leaves the same debug temp
bound multiple times.  Dunno if that is intent or just a bug.

	Jakub
diff mbox

Patch

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)