[GSoC] symbol to denote multiple operators

[Richard Biener]

On Fri, Jul 11, 2014 at 4:59 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On 7/11/14, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Thu, Jul 10, 2014 at 8:05 PM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> Hi,
>>>    I have attempted to add syntax for symbol to denote multiple
>>> operators.
>>>
>>> I tried it with few bogus patterns and it appears to work.... hopefully
>>> -:)
>>> eg: (bogus pattern):
>>> (for op in plus minus
>>>   (match_and_simplify
>>>     (op @0 @1)
>>>     (op @0 @0)))
>>>
>>> generates following patterns:
>>> (plus @0 @1) -> (plus @0 @0)  // simplify_0
>>> (plus @0 @1) -> (mult @0 @0)  // simplify_1
>>> (mult @0 @1) -> (plus @0 @0)  // simplify_2
>>> (mult @0 @1) -> (mult @0 @0)  // simplify_3
>>
>> s/mult/minus/?  I think it should only generate
>>
>>  (plus @0 @1) -> (plus @0 @0)
>>  (minus @0 @1) -> (minus @0 @0)
>>
>> to get the what you write we should need to write
>>
>>  (for op1 in plus minus
>>    (for op2 in plus minus
>>      (match_and_simplify
>>         (op1 @0 @1)
>>         (op2 @0 @0))))
>>
>>> root (0xab6b10), 0, 2
>>> |--(PLUS_EXPR) (0xab6b30), 1, 1
>>> |----true (0xab6ba0), 2, 1
>>> |------true (0xab6c10), 3, 2
>>> |--------simplify_0 { 0xab6ba0, 0xab6c10, (nil), (nil),  }  (0xab6c80), 4,
>>> 0
>>> |--------simplify_1 { 0xab6ba0, 0xab6c10, (nil), (nil),  }  (0xab6d40), 4,
>>> 0
>>> |--(MULT_EXPR) (0xab6d00), 1, 1
>>> |----true (0xab6d90), 2, 1
>>> |------true (0xab6e00), 3, 2
>>> |--------simplify_2 { 0xab6d90, 0xab6e00, (nil), (nil),  }  (0xab6e70), 4,
>>> 0
>>> |--------simplify_3 { 0xab6d90, 0xab6e00, (nil), (nil),  }  (0xab6f30), 4,
>>> 0
>>>
>>> * Changes to rest of the code:
>>> a) commutating patterns was interfering with this, because
>>> parse_match_and_simplify, immediately commutated match operand. Symbol
>>> should be replaced by operators before commutating. This required
>>> adjusting simplify (back to operand *match), and commutating is done
>>> in new function lower_commutative. Ideally this should be done during
>>> insertion in decision tree ?
>>
>> Yes, commutating should be done by inserting a pattern multiple
>> times with adjusted AST walk order.
>>
>>> b) adjustments required to e_operation constructor, so it doesn't
>>> call fatal, when it does not find id to be in the hash table.
>>
>> Eventually just temporarily insert a new operator in the hash table
>> when parsing comes along a (for OP ...?  That is, add a new kind,
>> USER and just re-use base->id?
>>
>>> * Caveats
>>> a) new e_operation constructor taking id_base * argument. Not sure
>>> if that's required.
>>> b) e_operation::user_id denotes user-defined identifier (<opname>),
>>> a rather apologetic name ...
>>> c) Similar to commutate(), replace_user_id() does not clone AST's.
>>> So we have multiple AST's sharing same nodes.
>>
>> I wonder if we want to parse the 'for' into an AST node instead,
>> thus not expand it on-the-fly.  Applying could then happen during
>> DT insertion.  Or as a separate lowering like you introduce
>> lower_commutative - that looks  cleaner.
>>
>> Or if we can simply parse the match-and-simplify multiple times, with
>> the for op replaces, using _cpp_backup_tokens.  Ok, no - that
>> sounds like too much of a hack.
>>
>>> * add multiple symbols ?
>>> should we have
>>> (for <opname> in operator-list1, <opname2> in operator-list2
>>>   (match_and_simplify
>>>      ...))
>>> or have nested for ?
>>> (for <opname> in operator-list1
>>>    (for <opname2> in operator-list2
>>>        (match_and_simplify
>>>           ....)))
>>
>> It depends on the desired semantics.  It's a lot clearer with
>> single opname for only (but then we eventually need nested for).
>>
>>> * we don't detect functions with wrong arguments
>>> for example, we dont give error on:
>>> (built_in_sqrt @0 @1)
>>> I guess that's because we don't have an easy way to figure out
>>> number of arguments a function expects ?
>>> (is there a built-in equivalent of tree_code_length[] ?)
>>
>> Yeah, the function stuff is still very simplistic and no, there isn't
>> any easy way of extracting the number of expected arguments
>> from builtins.def (it's encoded in the type).  The easiest way
>> would be to change builtins.def to add a number-of-args argument ...
>>
>> Let's just defer that issue.
>>
>>
>> As for the patch, we shouldn't do the cartesian_product - that's
>> hardly ever what the user intends and it means there isn't any
>> way of repeating the same pattern for multiple operators.
>>
>> A common use for 'for' would be (for OP in ne eq (...)) as most
>> equality foldings are valid for ne and eq.  Another is
>> for the various division kinds we have - trunc_div ceil_div floor_div
>> and round_div (same for mod):
>>
>> (for op in trunc_div ceil_div floor_div round_div
>>   (match_and_simplify
>>      (op @0 integer_onep)
>>      @0))
>>
>> (good example for match.pd to exercise the code)
>>
>> Can you fix the cartesian product thing (it should only simplify the
>> patch)?
> This version of the patch, removes cartesian_product, and reuses
> id_base::id for user-defined symbols.
>
> eg:
> (for op in plus minus
>   (match_and_simplify
>     (op (op @0 @1) @2)
>     (op @0 @0)))
>
> generates following patterns:
> (plus (plus @0 @1) @2) -> (plus @0 @0)
> (minus (minus @0 @1) @2) -> (minus @0 @0)
> Is this correct ?

Yes.

> I added the (for op in trunc_div floor_div ceil_div round_div ..)
> pattern in match.pd
> This works for trunc_div, I am not sure how to generate
> floor_div/ceil_div/round_div
> from C test-case.

Yeah, I think all of them may only appear with variable-length array
lowering.  No need to add testcases for them.

> I added the following rotate pattern in match.pd:
> /* (x << CNT1) OP (x >> CNT2) -> x r<< CNT1 OP being +, |, ^ */
> (for op in plus bit_ior bit_xor
> (match_and_simplify
>   (op:c (lshift @0 INTEGER_CST_P@1) (rshift @0 INTEGER_CST_P@2))
>   if (tree_fits_uhwi_p (@1) && tree_fits_uhwi_p (@2)
>       && tree_to_uhwi (@1) + tree_to_uhwi (@2) == TYPE_PRECISION (type))
>   (lrotate @0 @1)))
>
> Is this correct ?

it doesn't work for signed x (rshift is arithmetic shift).  So you miss
a TYPE_UNSIGNED (TREE_TYPE (@0)) check.  fold-const.c also
verifies that mode and type precision match (and makes sure to
use the vector/complex type element precision as shifts on
vectors shift their elements).  See around fold-const.c:10562.

I have fixed that, restricting it to integer types for now and committed
the patch.

Thanks,
Richard.

> * genmatch.c (id_base::id_kind): New enum value USER_DEFINED.
>     (e_operation::e_operation): Add default argument add_new_id.
>     (simplify): Remove member matchers.
>     (simplify): New member match.
>     (print_matches): Adjust to changes in simplify.
>     (decision_tree::insert): Likewise.
>     (parse_match_and_simplify): Likewise.
>     (lower_commutative): New function.
>     (check_operator): Likewise.
>     (replace_id): Likewise.
>     (eat_ident): Likewise.
>     (parse_for): Likewise.
>     (parse_expr): Call check_operator.
>     (main): Call parse_for, lower_commutative.
>
> * match.pd: Add pattern for div, and rotate pattern.
>
> [gcc/testsuite/gcc.dg/tree-ssa]
> * match-rotate.c: New test-case.
>
> Thanks and Regards,
> Prathamesh
>
>>
>> Thanks,
>> Richard.
>>
>>> * genmatch.c (e_operation::e_operation): New constructor.
>>> (e_operation::user_id): New member.
>>> (e_operation::get_op): New member function.
>>> (simplify::matchers): Remove.
>>> (simplify::match): New member.
>>> (lower_commutative): New function.
>>> (check_operator): Likewise.
>>> (replace_user_id): Likewise.
>>> (decision_tree::insert): Adjust to changes in simplify.
>>> (eat_ident): New function.
>>> (parse_expr): Call to check_operator.
>>> (parse_for): New function.
>>> (main): Add calls to parse_for, lower_commutative.
>>>
>>> Thanks and Regards,
>>> Prathamesh
>>