Re: Move some bit and binary optimizations in simplify and match

[Richard Biener <richard dot guenther at gmail dot com>]

On Wed, Oct 21, 2015 at 8:48 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Tue, 20 Oct 2015, Richard Biener wrote:
>
>> On Tue, Oct 20, 2015 at 8:46 AM, Hurugalawadi, Naveen
>> <Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>>
>>> Hi,
>>>
>>>>> +/* Fold X + (X / CST) * -CST to X % CST.  */
>>>>> This one is still wrong
>>>
>>> Removed.
>>>
>>>>> I don't understand the point of the FLOAT_TYPE_P check.
>>>
>>> The check was there in fold-const. So, just had the same check.
>>>
>>>>> Will we also simplify (A & B) - (A & ~B) into B - (A ^ B) ?
>>>
>>> Done.
>>>
>>>>> or maybe integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1))
>>>
>>> Done.
>>>
>>>>> :c on bit_ior? It should also allow you to merge the 2 CST versions
>>>>> into one.
>>>
>>> Had it. But due to the error on "logical_inverted_value"; confused it
>>> with
>>> this pattern and had duplicated it.
>>>
>>>>> I am not really in favor of the indentation change (or the comment).
>>>
>>> Done.
>>>
>>>>> This patch is ok when bootstrapped / tested and with a proper changelog
>>>>> entry.
>>>
>>> Regression tested on X86_64 with no extra failures.
>>
>>
>> +(simplify
>> + (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
>> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
>> +  (minus (bit_xor @0 @1) @1)))
>>
>> use if (wi::bit_and (@2, @1) == 0)
>
>
> I believe the original transformation required @1 and @2 to be bit_not
> of each other, so this might not work.

Oh, sorry - indeed.  It fails for @2 == @1 == 0.  So using bit_xor
is required or simply wi::bit_not (@2) == @1.

> He had a suitable test using wi,
> it is my fault he changed it (sorry for not being clear enough that my
> remark wasn't meant as a patch). The reason was so we could change
> INTEGER_CST to CONSTANT_CLASS_P and handle vectors.

I realized that but until that happens we should stick with the faster and
simpler wi:: interface.  The tree interface will allocate extra garbage
for computing the BIT_XOR_EXPR even when no transform is done
thus I believe we'd want a integer_bit_not_of_the_other () function
avoiding extra tree garbage in the end.

>> and instead of the 2nd group
>>
>> +/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
>> +(simplify
>> + (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1)))
>> +  (minus @1 (bit_xor @0 @1)))
>> +(simplify
>> + (minus (bit_and:s @0 INTEGER_CST@1) (bit_and:s @0 INTEGER_CST@2))
>> + (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
>> +  (minus @1 (bit_xor @0 @1))))
>>
>> place a :c on the minus of the one not matching INTEGER_CSTs.
>
>
> Will that really work?

Yes.  The :c will create a 2nd pattern with the ops of the minus swapped, thus

/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
(simplify
 (minus:c (bit_and:s @0 (bit_not @1)) (bit_and:s @0 @1))
  (minus (bit_xor @0 @1) @1))
(simplify
 (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
 (if (integer_all_onesp (const_binop (BIT_XOR_EXPR, type, @2, @1)))
  (minus (bit_xor @0 @1) @1)))

will implicitely add

(simplify
 (minus (bit_and:s @0 @1) (bit_and:s @0 (bit_not @1))
  (minus (bit_xor @0 @1) @1))

hmm, but that isn't correct for @1 == 0?  So the fold-const.c code is incorrect.

Note it doesn't trigger for

int foo (int a, int b)
{
  return (a & ~b) - (a & b);
}

because canonicalization makes it appear as (~b & a) - (a & b) and the
fold-const.c
fails to have a :c on the bit_and with the bit_not (you too).

Note how the fold-const.c code doesn't care about where the ~ is placed (and for
constants there isn't any explicit ~ anyway).

The code triggers on

int foo (int a, int b)
{
  return ((a+1) & ~b) - ((a+1) & b);
}
int bar (int a, int b)
{
  return ((a+1) & b) - ((a+1) & ~b);
}

and correctly it seems.  The key is that it explicitely uses bit_not
of the first
ops b or ~b while the pattern tries to be clever and re-uses the present
bit_not - _this_ doesn't play well with using :c.

Still the duplicate INTEGER_CST pattern is not necessary.

So I suggest to modify your patch to do

+/* Fold (A & ~B) - (A & B) into (A ^ B) - B.  */
+(simplify
+ (minus (bit_and:cs @0 (bit_not @1)) (bit_and:s @0 @1))
+  (minus (bit_xor @0 @1) @1))
+(simplify
+ (minus (bit_and:s @0 INTEGER_CST@2) (bit_and:s @0 INTEGER_CST@1))
+ (if (wi::bit_not (@2) == @1)
+  (minus (bit_xor @0 @1) @1)))
+
+/* Fold (A & B) - (A & ~B) into B - (A ^ B).  */
+(simplify
+ (minus (bit_and:s @0 @1) (bit_and:cs @0 (bit_not @1)))
+  (minus @1 (bit_xor @0 @1)))

Richard.

>
> --
> Marc Glisse