Re: [PATCH] Fix PR77826

[Marc Glisse <marc.glisse@inria.fr>]

On Tue, 11 Oct 2016, Richard Biener wrote:

>> An example that regressed at -O (looking at the .optimized dump)
>>
>> int f(int a, unsigned b){
>>   a &= 1;
>>   b &= 1;
>>   return a&b;
>> }
>
> Yeah, but it usually also shows a badly written pattern:
>
> /* (X & Y) & (X & Z) -> (X & Y) & Z
>   (X | Y) | (X | Z) -> (X | Y) | Z  */
> (for op (bit_and bit_ior)
> (simplify
>  (op:c (convert1?@3 (op:c@4 @0 @1)) (convert2?@5 (op:c@6 @0 @2)))
>  (if (tree_nop_conversion_p (type, TREE_TYPE (@1))
>       && tree_nop_conversion_p (type, TREE_TYPE (@2)))
>
> so how could we ever match the @0s when we have either of the two
> conversions not present?  We could only do this then facing constants
> (due to using operand_equal_p).  We for example fail to handle
>
> (X & Y) & (unsigned) ((singed)X & Z)

Indeed... (oups, looks like I wrote that one)

Trying to find other examples

/* Fold A - (A & B) into ~B & A.  */
(simplify
  (minus (convert? @0) (convert?:s (bit_and:cs @0 @1)))
  (if (tree_nop_conversion_p (type, TREE_TYPE (@0))
       && tree_nop_conversion_p (type, TREE_TYPE (@1)))
   (convert (bit_and (bit_not @1) @0))))

Hmm, should be convert1/convert2 to handle the case where @0 is a 
constant.

/* (X | Y) ^ X -> Y & ~ X*/
(simplify
  (bit_xor:c (convert? (bit_ior:c @0 @1)) (convert? @0))
  (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))
   (convert (bit_and @1 (bit_not @0)))))

Again, will never match when there is a convert and @0 is a constant.

(for op (bit_and bit_ior bit_xor)
      rop (bit_ior bit_and bit_and)
  (simplify
   (op (convert? (rop:c @0 @1)) (convert? (rop:c @0 @2)))
...

Again won't match for constant @0 that has a different type in both parts.

/* (X & Y) & Y -> X & Y
    (X | Y) | Y -> X | Y  */
(for op (bit_and bit_ior)
  (simplify
   (op:c (convert?@2 (op:c @0 @1)) (convert? @1))
   @2))

Same issue.

Ok, not many transformations are concerned, and most need a rewrite 
anyway...

In the other direction, looking at the transformations for which we used 
explicitly operand_equal_p as a workaround for lax integer constant 
matches, it doesn't look like changing them back to use matching captures 
would help, it would require duplicating the pattern for constants.

>> If we stick to the old behavior, maybe we could have some genmatch magic to
>> help with the constant capture weirdness. With matching captures, we could
>> select which operand (among those supposed to be equivalent) is actually
>> captured more cleverly, either with an explicit marker, or by giving priority
>> to the one that is not immediatly below convert? in the pattern.
>
> This route is a difficult one to take

The simplest version I was thinking about was @0 for a true capture, and 
@@0 for something that just has to be checked for equality with @0.

> -- what would be possible is to
> capture a specific operand.  Like allow one to write
>
> (op (op @0@4 @1) (op @0@3 @2))
>
> and thus actually have three "names" for @0.  We have this internally
> already when you write
>
> (convert?@0 @1)
>
> for the case where there is no conversion.  @0 and @1 are the same
> in this case.

Looks nice and convenient (assuming lax constant matching).

> Not sure if this helps enough cases.

IIRC, in all cases where we had trouble with operand_equal_p, chosing 
which operand to capture would have solved the issue.

> I still think that having two things matched that are not really
> the same is werid (and a possible source of errors as in, ICEs,
> rather than missed optimizations).

Ok. Let's go with the strict matching, it is indeed less confusing.

>> And if we move to stricter matching, maybe genmatch could be updated so
>> convert could also match integer constants in some cases.
>
> You mean when trying to match @0 ... (convert @0) and @0 is an INTEGER_CST
> allow then (convert ...) case to match an INTEGER_CST of different type?
> That's an interesting idea (not sure how to implement that though).

Yes, though I am not sure of the exact semantics that would work best.

On a related note, seeing duplicated patterns for constants, I tried 
several variants of

(match (mynot @0)
  (bit_not @0))
(match (mynot @0)
  INTEGER_CST@0
  (if (@0 = wide_int_to_tree (TREE_TYPE (@0), wi::bit_not (@0)))))

(simplify
  (minus (bit_and:cs @0 (mynot @1)) (bit_and:cs @0 @1))
   (minus (bit_xor @0 @1) @1))

This kind of hack feels wrong, but I don't see a proper way to write it.


>>> I agree that some transforms would need updates - I've actually tried
>>> to implement a warning for genmatch whenever seeing a match with
>>> (T)@0 but there isn't any good existing place to sneak that in.
>>
>>
>>>>> 	* match.pd ((X /[ex] A) * A -> X): Properly handle converted
>>>>> 	and constant A.
>>>>
>>>> This regressed
>>>> int f(int*a,int*b){return 4*(int)(b-a);}
>>>
>>> This is because (int)(b-a) could be a truncation in which case
>>> multiplying with 4 might not result in the same value as
>>> b-a truncated(?).  The comment before the unpatched patterns
>>> said "sign-changing conversions" but nothign actually verified this.
>>> Might be that truncations are indeed ok now that I think about it.
>>
>> 2015-05-22  Marc Glisse  <marc.glisse@inria.fr>
>>
>>         PR tree-optimization/63387
>>         * match.pd ((X /[ex] A) * A -> X): Remove unnecessary condition.
>>
>> Apparently I forgot to remove the comment at that time :-(
>
> Ok.  I'm now testing a patch to remove the restriction again (and adjust
> the comment).

Thanks. (since exact_div is used almost only with constant divisors, the 
old pattern was fine before strict matching, but indeed your more general 
pattern is better)


-- 
Marc Glisse