Re: writing patterns

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

On Thu, Jul 31, 2014 at 2:44 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Jul 31, 2014 at 11:09 AM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>> On Thu, Jul 31, 2014 at 2:15 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Thu, Jul 31, 2014 at 7:41 AM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> On Wed, Jul 30, 2014 at 11:49 PM, Prathamesh Kulkarni
>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>> On Wed, Jul 30, 2014 at 4:49 PM, Richard Biener
>>>>> <richard.guenther@gmail.com> wrote:
>>>>>> On Wed, Jul 30, 2014 at 1:11 PM, Richard Biener
>>>>>> <richard.guenther@gmail.com> wrote:
>>>>>>> On Wed, Jul 30, 2014 at 12:49 PM, Prathamesh Kulkarni
>>>>>>> <bilbotheelffriend@gmail.com> wrote:
>>>>>>>> Hi,
>>>>>>>>    Sorry to ask a stupid question, but I am having issues writing patterns
>>>>>>>> involving casts. I am trying to write patterns from simplify_rotate.
>>>>>>>>
>>>>>>>> Could you show me how to write a patterns that involve
>>>>>>>> casts ?
>>>>>>>> for eg:
>>>>>>>> ((T) ((T2) X << CNT1)) + ((T) ((T2) X >> CNT2))     iff CNT1 + CNT2 == B
>>>>>>>> T -> some unsigned type with bitsize B, and some type T2 wider than T.
>>>>>>>> How to express this in the pattern ?
>>>>>>>
>>>>>>> [copying gcc@ because of the syntax stuff]
>>>>>>>
>>>>>>> for example with (leaving captures as the appear in the pattern above)
>>>>>>>
>>>>>>> (match_and_simplify
>>>>>>>    (plus (convert@2 (lshift (convert@0 X) CNT1))
>>>>>>>            (convert (rshift (convert@1 X) CNT2)))
>>>>>>>     /* Types T2 have to match */
>>>>>>>    (if (types_compatible_p (TREE_TYPE (@0), TREE_TYPE (@1))
>>>>>>>         /* Type T should be unsigned.  */
>>>>>>>        && TYPE_UNSIGNED (TREE_TYPE (@2))
>>>>>>>        /* T2 should be wider than T.  */
>>>>>>>        && TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (TREE_TYPE (@2))
>>>>>>>        /* CNT1 + CNT2 == B */
>>>>>>>        && wi::eq_p (TYPE_PRECISION (TREE_TYPE (@2)),
>>>>>>>                            wi::add (CNT1, CNT2))))
>>>>>>>    (lrotate CNT1))
>>>>>>
>>>>>> Note that this will _explicitely_ require a conversion.  That is, if T == T2
>>>>>> it won't match because the conversion to T will not be there, nor if X
>>>>>> is already of type T2.
>>>>>>
>>>>>> Which means that we want to match multiple variants of this
>>>>>> (with conversions in place or not).  Hmm.  Maybe with extending 'for' like
>>>>>>
>>>>>> (for cvt1 in convert *
>>>>>>   (fot cvt2 in convert *
>>>>>>     (plus@2 (cvt1 (lshift@0 (cvt2 X) CNT1))
>>>>>>                  (cvt1 (rshift@1 (cvt2 X) CNT2)))
>>>>>> ...
>>>>>>
>>>>>> adding an "empty" operator to the list of operators to substitute for cvt1
>>>>>> and allowing nested for.  The "empty" operator would necessarily be
>>>>>> unary and be just un-wrapped.
>>>>> Would it be better to have syntax (say using ?) for denoting that an
>>>>> operator is optional ?
>>>>> operator should be unary, and it's operand must be an expression.
>>>>>
>>>>> so the pattern becomes sth like:
>>>>> (plus@2 (convert? (lshift@0 (convert? X) CNT1))
>>>>>              (convert? (rshift@1 (convert? X) CNT2)))
>>>>>
>>>> Let me rephrase it.
>>>> An operator can be marked optional, if
>>>> a) it's unary
>>>> b) if in outermost-expr, the operand must be an expression
>>>>
>>>> I want to reject case like:
>>>> (negate? @0)
>>>>
>>>> (op? operand)
>>>> generates code :
>>>> match (op)
>>>>    match (operand)
>>>>
>>>> and once without op
>>>> match (operand)
>>>>
>>>> Implementation-wise I think, we could duplicate the AST, like we do
>>>> for "for pattern".
>>>> Would that be okay ?
>>>
>>> I thought of something similar but how exactly would you do the
>>> duplication in the above example?  The point is that we know
>>> that the conversions will exist in pairs, that is, either
>>> the two outer and no inner or no outer and both inner or
>>> both outer and both inner.  You can express that with the
>>> nested for - with just a '?' you can't do that.  Of course you could
>>> do sth like
>>>
>>> (plus@2 (convert?1 (lshift@0 (convert?2 X) CNT1))
>>>              (convert?1 (rshift@1 (convert?2 X) CNT2)))
>>>
>>> that is, add an index to ?s and tie them together.  We want to
>>> avoid generating useless patterns - in this case 4 are sufficient
>>> but if we generate all possible combinations we'd have an additional
>>> 12 useless patterns.
>> Ah yes, didn't realize that, thanks.
>>>
>>> But using '?' indeed looks better than (ab)using 'for'.  Note that
>>> it is _only_ 'convert' that I can see this useful for (or can you
>>> think of other cases?).  So maybe we instead want to make
>>> it a special operator like
>>>
>>> (plus@2 (opt_convert 1 (lshift@0 (opt_convert 2 X) CNT1))
>>>              (opt_convert 1 (rshift@1 (opt_convert 2 X) CONT2)))
>>>
>>> with an additional operand specifying the group (or simply
>>> have opt_convert1 and opt_convert2 operands - hoping for
>>> more "groups" to never happen ;)).
>>>
>>> Actually I like opt_convert[123] most.
>> I like opt_convert[123] too.
>> Implementation-wise I don't think it would be more difficult to
>> generalize it for other operators ...
>
> Of course, but I don't see the need for that.  Conversions are really
> special in this regard.
>
>> I was thinking about this ... Instead of grouping by indexes,
>> how about defining operator aliases ?
>> sth like:
>> (define_op cvt1 convert)
>> (define_op cvt2 convert)
>>
>> and then the pattern becomes:
>>
>> (plus@2 (cvt1? (lshift@0 (cvt2? X) CNT1))
>>              (cvt1? (rshift@1 (cvt2? X) CNT2)))
>>
>> that would avoid generating useless patterns (since cvt1, cvt2 are
>> "different"), however during code-gen
>> both shall map to CONVERT_EXPR (and once without it since its optional).
>
> Yeah, that would work if we'd implement it that way.  Still I don't like
> a general '?' facility unless we come up with really good uses apart from
> conversions.
Agreed. I will start with implementing opt_convert.

Thanks,
Prathamesh.
>
> Richard.
>
>> Thanks,
>> Prathamesh
>>
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>> Prathamesh
>>>>
>>>>
>>>>> Thanks,
>>>>> Prathamesh
>>>>>
>>>>>>
>>>>>> Extending for in this way avoids treating conversions specially
>>>>>> (I don't see an easy way to do very good at that automagically).  We
>>>>>> need multiple patterns in the decision tree here anyway.
>>>>>>
>>>>>> Now guess sth fancy in place of '*' ...
>>>>>>
>>>>>> Lisp style would be less free-form like
>>>>>>
>>>>>> (for cvt (convert ())
>>>>>>
>>>>>> where we could use an empty list for the "empty" operator.
>>>>>>
>>>>>> Is nested for support already implemented?
>>>>>>
>>>>>> Thanks,
>>>>>> Richard.
>>>>>>
>>>>>>> which suggests that we may want to add some type capturing / matching
>>>>>>> so we can maybe write
>>>>>>>
>>>>>>>   (plus (convert@T (lshift (convert@T2 X) CNT1))
>>>>>>>           (convert (rshift (convert@T2 X) CNT2)))
>>>>>>>   (if (/* T2s will be matched automagically */
>>>>>>>        && TYPE_UNSIGNED (@T)
>>>>>>>        && TYPE_PRECISION (@T2) > TYPE_PRECISION (@T)
>>>>>>>        && wi::eq_p (TYPE_PRECISION (@T), wi::add (CNT1, CNT2))))
>>>>>>>
>>>>>>> which is less to type and supports requiring matching types.  Maybe
>>>>>>> require @T[0-9]+ here thus use @T0 and disallow plain @T.  We could
>>>>>>> then also use @T for the implicitely "captured" outermost type we
>>>>>>> refer to as plain 'type' right now.
>>>>>>>
>>>>>>> I suggest to go ahead without a new syntax for now and see if it
>>>>>>> gets unwieldingly ugly without first.
>>>>>>>
>>>>>>>> For this week, I have planned:
>>>>>>>> a) writing patterns from simplify_rotate
>>>>>>>> b) replacing op in c_expr
>>>>>>>> c) writing more test-cases.
>>>>>>>>
>>>>>>>> If there's anything else you would like me to do, I would be happy
>>>>>>>> to know.
>>>>>>>
>>>>>>> Just keep an eye open for things like above - easy ways to reduce
>>>>>>> typing for patterns.
>>>>>>>
>>>>>>> Btw, I suggest to split up match.pd by code you converted from.  Thus
>>>>>>> for simplify_rotate add
>>>>>>>
>>>>>>>   match-simplify-rotate.pd
>>>>>>>
>>>>>>> with the patterns and do a #include "match-simplify-rotate.pd"
>>>>>>> in match.pd.  That will make it easier to match the two later.
>>>>>>>
>>>>>>> Thanks,
>>>>>>> Richard.
>>>>>>>
>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> Prathamesh