predicates on expressions ?

[Prathamesh Kulkarni]

On Tue, Jul 15, 2014 at 6:05 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jul 14, 2014 at 3:05 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Jul 14, 2014 at 12:07 PM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> I was wondering if it was a good idea to implement
>>> predicate on expressions ?
>>>
>>> Sth like:
>>> (match_and_simplify
>>>   (op (op2:predicate @0))
>>>   transform)
>>>
>>> instead of:
>>> (match_and_simplify
>>>   (op (op2@1 @0))
>>>   if (predicate (@1))
>>>   transform)
>>>
>>> When predicate is simple as just being a macro/function,
>>> we could use this style and when the predicate is more complex
>>> resort to using if-expr (or write the predicate as macro in gimple-match-head.c
>>> and use the macro in pattern instead ...)
>>>
>>> Example:
>>> we could rewrite the pattern
>>> (match_and_simplify
>>>   (plus:c @0 (negate @1))
>>>   if (!TYPE_SATURATING (type))
>>>   (minus @0 @1))
>>>
>>> to
>>>
>>> (match_and_simplify
>>>   (plus:c:NOT_TYPE_SATURATING_P @0 (negate @1))
>>>   (minus @0 @1))
>>>
>>> with NOT_TYPE_SATURATING_P predicate defined
>>> appropriately in gimple-match-head.c
>>>
>>> However I am not entirely sure if adding predicates on expressions
>>> would be very useful....
>>
>> Well.  I think there are two aspects to this.  First is pattern
>> readability where I think that the if-expr form is more readable.
>> Second is the ability to do less work in the code generated
>> from the decision tree.
>>
>> For example most of the patterns from associate_plusminus
>> still miss the !TYPE_SATURATING && !FLOAT_TYPE_P &&
>> !FIXED_POINT_TYPE_P if-expr.  That is, we'd have
>>
>> /* (A +- B) - A -> +-B.  */
>> (match_and_simplify
>>   (minus (plus @0 @1) @0)
>>   if (!TYPE_SATURATING (type)
>>       && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
>>   @1)
>> (match_and_simplify
>>   (minus (minus @0 @1) @0)
>>   if (!TYPE_SATURATING (type)
>>       && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
>>   (negate @1))
>> /* (A +- B) -+ B -> A.  */
>> (match_and_simplify
>>   (minus (plus @0 @1) @1)
>>   if (!TYPE_SATURATING (type)
>>       && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
>>   @0)
>> (match_and_simplify
>>   (plus:c (minus @0 @1) @1)
>>   if (!TYPE_SATURATING (type)
>>       && !FLOAT_TYPE_P (type) && !FIXED_POINT_TYPE_P (type))
>>   @0)
>>
>> with code-generation checking the if-expr after matching.  And
>> with using expression predicates we'd be able to check the
>> predicate when matching the outermost 'minus' and "CSE"
>> the predicate check for the first three patterns.  Runtime-wise
>> it depends on whether there is a point to back-track to.
>
> Actually now that I look at the current state of the testsuite on the
> branch and notice
>
> FAIL: gcc.c-torture/execute/20081112-1.c execution,  -O1
>
> which points at
>
> (match_and_simplify
>   (plus (plus @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
>   (plus @0 (plus @1 @2))
>
> which we may not apply to (a - 1) + INT_MIN as -1 + INT_MIN
> overflows and a + (-1 + INT_MIN) then introduces undefined
> signed integer overflow.  tree-ssa-forwprop.c checks TREE_OVERFLOW
> on the result of (plus @1 @2) and disables the simplification
> properly.  We can do the same with re-writing the pattern to
>
> (match_and_simplify
>   (plus (plus @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
>   /* If the constant operation overflows we cannot do the transform
>      as we would introduce undefined overflow, for example
>      with (a - 1) + INT_MIN.  */
>   if (!TREE_OVERFLOW (@1 = int_const_binop (PLUS_EXPR, @1, @2)))
>   (plus @0 @1))
>
> also using something I'd like to more formally allow (re-using sth
> computed in the if-expr in the replacement).  But of course writing
> it this way is ugly and the following would be nicer?
>
> (match_and_simplify
>   (plus (plus @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
>   (plus @0 (plus:!TREE_OVERFLOW @1 @2)))
>
> ?  That would be predicates on replacement expressions ...
> (also negated predicates).
Or maybe allow intermingling c-expr and expr ?
(match_and_simplify
   (plus (plus @0 INTEGER_CST_P@1) INTEGER_CST_P@2)
   /* If the constant operation overflows we cannot do the transform
      as we would introduce undefined overflow, for example
      with (a - 1) + INT_MIN.  */
    {
       tree sum;
       sum = int_const_binop (PLUS_EXPR, @1, @2);
       if (!TREE_OVERFLOW (sum))
         (plus @0 @1)
       else
          FAIL;
     })

However the predicates version looks better, compared to others...

Thanks and Regards,
Prathamesh
> Now it doesn't look all-that-pretty :/
>
> Another possibility is to always fail if TREE_OVERFLOW constants
> leak into the replacement IL.  (but I'd like to avoid those behind-the-backs
> things at the moment)
>
> Richard.