Move some bit and binary optimizations in simplify and match

Hi,

Please find attached the patch that moves some more patterns from
fold-const using simplify and match.

Please review the patch and let me know if any modifications are required.

Tested the patch on X86 without any regressions.

Thanks,
Naveen

ChangeLog

2015-10-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	* fold-const.c (fold_binary_loc) : Move X + (X / CST) * -CST ->
	X % CST to match.pd.
	Move Fold (A & ~B) - (A & B) into (A ^ B) - B to match.pd.
	Move (-A) * (-B) -> A * B to match.pd.
	Move (a * (1 << b)) is (a << b) to match.pd.
	Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
	Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.
	Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
	Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.
	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
	Move Fold X & (Y ^ X) as ~Y & X to match.pd.

	* match.pd (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1)
	(negate @1))): New simplifier.
	(minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) :
	New simplifier.
	(mult:c @0 (lshift integer_onep@1 @2)): New simplifier.
	(mult:c (plus @0 @0) INTEGER_CST@1): New simplifier.
	(mult (rdiv REAL_CST@0 @1) REAL_CST@2): New simplifier.
	(bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
	: New simplifier.
	(bit_and:c @0 (bit_not:s @0)): New simplifier.
	(bit_and:c @0 (eq @0 integer_zerop@1)): New simplifier.
	(bit_and @0 (bit_xor:s @0 @1)): New simplifier.
	(bit_and @0 (bit_xor:s @1 @0)): New simplifier.
	(mult:c (negate @0) (negate @1)): New simplifier.

On Wed, Oct 7, 2015 at 11:54 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
> Please find attached the patch that moves some more patterns from
> fold-const using simplify and match.
>
> Please review the patch and let me know if any modifications are required.

+/* Fold X + (X / CST) * -CST to X % CST.  */
+(simplify
+ (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1) (negate @1)))

that's a bit too literal -- (negate @1) won't match for -@1

+  (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
+  (trunc_mod @0 @1)))

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1))
+  (if (! FLOAT_TYPE_P (type))
+  (minus (bit_xor @0 @1) @1)))

Likewise the fold code handles both constant and non-constant B.
To mimic this you need a second pattern for the constant case
or add a predicate matching @1 with ~@1.

+/* (-A) * (-B) -> A * B  */
+(simplify
+ (mult:c (negate @0) (negate @1))
+  (mult @0 @1))

the fold-const.c code handles sign-conversions around the negates
so you should add (convert?)s around them and verify useless_type_conversions.

+/* Fold (a * (1 << b)) into (a << b)  */
+(simplify
+ (mult:c @0 (lshift integer_onep@1 @2))
+  (if (! FLOAT_TYPE_P (type))
+  (lshift @0 @2)))

Likewise (sign-conversion on the lshift).  Though I'm not sure
this won't trap ubsan for signed left-shift of negative values.

+/* Fold (C1/X)*C2 into (C1*C2)/X.  */
+(simplify
+ (mult (rdiv REAL_CST@0 @1) REAL_CST@2)
+  (if (FLOAT_TYPE_P (type)
+       && flag_associative_math)
+  (rdiv (mult @0 @2) @1)))

the fold-const.c code avoids the transform if @0 * @2 doesn't simplify
(nans/infs and flag combos).  Not sure if we care though.

+/* Simplify (X & ~Y) | (~X & Y) is X ^ Y.  */
+(simplify
+ (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
+  (bit_xor @0 @1))

fold again handles also constants for X and Y.  I suggest to re-use
the matching predicate you need to add for the above ~ pattern.
fold also handles sign-converted bit-ands.

+/* Simplify ~X & X as zero.  */
+(simplify
+ (bit_and:c @0 (bit_not:s @0))
+  { build_zero_cst (type); })

I was sure we already have this...  looks I was wrong.  Again fold
handles sign-conversions on @0 resp. the bit_not.

+/* Simplify (X == 0) & X as zero.  */
+(simplify
+ (bit_and:c @0 (eq @0 integer_zerop@1))
+  @1)

I think we have this one see logical_inverted_value and uses:

(simplify
 (bit_and:c @0 (logical_inverted_value @0))
 { build_zero_cst (type); })

+/* Fold X & (X ^ Y) as X & ~Y.  */
+(simplify
+ (bit_and @0 (bit_xor:s @0 @1))
+  (bit_and @0 (bit_not @1)))
+
+/* Fold X & (Y ^ X) as ~Y & X.  */
+(simplify
+ (bit_and @0 (bit_xor:s @1 @0))
+  (bit_and (bit_not @1) @0))

add :c on the bit_and and the bit_xor and then merge the patterns.

Thanks,
Richard.




> Tested the patch on X86 without any regressions.
>
> Thanks,
> Naveen
>
> ChangeLog
>
> 2015-10-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         * fold-const.c (fold_binary_loc) : Move X + (X / CST) * -CST ->
>         X % CST to match.pd.
>         Move Fold (A & ~B) - (A & B) into (A ^ B) - B to match.pd.
>         Move (-A) * (-B) -> A * B to match.pd.
>         Move (a * (1 << b)) is (a << b) to match.pd.
>         Move convert (C1/X)*C2 into (C1*C2)/X to match.pd.
>         Move (X & ~Y) | (~X & Y) is X ^ Y to match.pd.
>         Move ~X & X, (X == 0) & X, and !X & X are zero to match.pd.
>         Move X & ~X , X & (X == 0), and X & !X are zero to match.pd.
>         Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>         Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>
>         * match.pd (plus @0 (mult:s (trunc_div:s @0 INTEGER_CST@1)
>         (negate @1))): New simplifier.
>         (minus (bit_and:s @0 (bit_not:s @1)) (bit_and:s @0 @1)) :
>         New simplifier.
>         (mult:c @0 (lshift integer_onep@1 @2)): New simplifier.
>         (mult:c (plus @0 @0) INTEGER_CST@1): New simplifier.
>         (mult (rdiv REAL_CST@0 @1) REAL_CST@2): New simplifier.
>         (bit_ior (bit_and:s @0 (bit_not:s @1)) (bit_and:s (bit_not:s @0) @1))
>         : New simplifier.
>         (bit_and:c @0 (bit_not:s @0)): New simplifier.
>         (bit_and:c @0 (eq @0 integer_zerop@1)): New simplifier.
>         (bit_and @0 (bit_xor:s @0 @1)): New simplifier.
>         (bit_and @0 (bit_xor:s @1 @0)): New simplifier.
>         (mult:c (negate @0) (negate @1)): New simplifier.

On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
> 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
> 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.

I wonder if we shouldn't try to autogenerate patterns such as these. I 
did something like that for a different project a long time ago. 
Generate expressions up to a certain level of complexity, identify which 
ones are equivalent, and pick the one with the lowest cost for 
simplifications...


Bernd

On Thu, 8 Oct 2015, Bernd Schmidt wrote:

> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
> > 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
> > 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.
> 
> I wonder if we shouldn't try to autogenerate patterns such as these. I did
> something like that for a different project a long time ago. Generate
> expressions up to a certain level of complexity, identify which ones are
> equivalent, and pick the one with the lowest cost for simplifications...

Any bitwise expression whose ultimate operands are X, Y, 0 and -1 
(possibly with conversions among types of the same width) could be 
canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where 
A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best 
canonical forms, but if you're folding this sort of expression you ought 
to be able to make GCC fold all such expressions down to some such form 
(and fold away all equality comparisons among such expressions with 
constant value).

Now, such canonicalization could be done with a finite number of 
autogenerated patterns (if you can fold ~(A BINOP B), (A BINOP B) BINOP C 
and (A BINOP B) BINOP (C BINOP D), for A, B, C, D from 0, -1, X, Y, ~X, 
~Y, folding for more complicated expressions falls out).  I don't know if 
that's the best way to do such folding or not.

Given such folding, autogenerating expressions of the form ((A BINOP B) 
BINOP (C BINOP D)) == CANONICAL_FORM seems a plausible way of getting 
testsuite coverage for the folding (and for that matter for seeing what 
such folding is missing at present).

On 10/08/2015 08:03 PM, Joseph Myers wrote:
> On Thu, 8 Oct 2015, Bernd Schmidt wrote:
>
>> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
>>> 	Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>>> 	Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>>
>> I wonder if we shouldn't try to autogenerate patterns such as these. I did
>> something like that for a different project a long time ago. Generate
>> expressions up to a certain level of complexity, identify which ones are
>> equivalent, and pick the one with the lowest cost for simplifications...
>
> Any bitwise expression whose ultimate operands are X, Y, 0 and -1
> (possibly with conversions among types of the same width) could be
> canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where
> A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best
> canonical forms, but if you're folding this sort of expression you ought
> to be able to make GCC fold all such expressions down to some such form
> (and fold away all equality comparisons among such expressions with
> constant value).

I was actually thinking of also doing this for more complex expressions 
with more than two different operands.


Bernd

On Thu, Oct 8, 2015 at 8:15 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> On 10/08/2015 08:03 PM, Joseph Myers wrote:
>>
>> On Thu, 8 Oct 2015, Bernd Schmidt wrote:
>>
>>> On 10/07/2015 11:54 AM, Hurugalawadi, Naveen wrote:
>>>>
>>>>         Move Fold X & (X ^ Y) as X & ~Y to match.pd.
>>>>         Move Fold X & (Y ^ X) as ~Y & X to match.pd.
>>>
>>>
>>> I wonder if we shouldn't try to autogenerate patterns such as these. I
>>> did
>>> something like that for a different project a long time ago. Generate
>>> expressions up to a certain level of complexity, identify which ones are
>>> equivalent, and pick the one with the lowest cost for simplifications...
>>
>>
>> Any bitwise expression whose ultimate operands are X, Y, 0 and -1
>> (possibly with conversions among types of the same width) could be
>> canonicalized to one of: 0, -1, X, Y, ~X, ~Y, X^Y, X^~Y, A&B or A|B (where
>> A is X or ~X and B is Y or ~Y).  I don't guarantee those are the best
>> canonical forms, but if you're folding this sort of expression you ought
>> to be able to make GCC fold all such expressions down to some such form
>> (and fold away all equality comparisons among such expressions with
>> constant value).
>
>
> I was actually thinking of also doing this for more complex expressions with
> more than two different operands.

Note that the optimization problem in general is more complicated and
involves multiple such expressions which should be associated/optimized
with CSE in mind to result in the minimal number of overall instructions
needed to compute all required values.

But yes, we could auto-generate patterns up to a specific depth or up
to a point where more complex patterns are handled by composition.
Patches welcome ;)

Richard.

>
> Bernd