This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: writing patterns


On Mon, Aug 4, 2014 at 4:44 PM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Mon, Aug 4, 2014 at 2:59 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Aug 4, 2014 at 12:16 AM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>>> On Thu, Jul 31, 2014 at 2:49 PM, Prathamesh Kulkarni
>>> <bilbotheelffriend@gmail.com> wrote:
>>>> 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.
>>> I have attached patch, that implements opt_convert.
>>> The implementation is not very efficient (i hope we can combine
>>> replace_opt_convert and lower_opt_convert).
>>>
>>> Some issues with implementation:
>>> a) since OPT_CONVERT is not defined in tree.def, i added it after
>>> #include tree.def in enum tree_code.
>>> So our enum tree_code becomes different from the usual enum tree_code.
>>>
>>> b) checks if there's any opt_convert remaining before lowering it to CONVERT
>>> and once removing it (this leads to walking AST thrice per each group).
>>> We can probably combine lower_opt_convert, remove_opt_convert and
>>> has_opt_convert into one function.
>>>
>>> c) opt_convert cannot be captured, for instance doesn't make sense
>>> when it's operand is not an expression
>>> eg - (opt_convert 1 @0)
>>> Or maybe allow capturing if the operand is expression ?
>>
>> Hmm.  Capturing the convert may be necessary though as we usually
>> have to constrain allowed conversions.  Like
>>
>>  (convert?@0 @1)
>>  if (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (TREE_TYPE (@1))
>>
>> to allow an optional widening convertsion.  But yes, we can't
>> possibly evaluate that if-expression if the convert is not there.
>>
>> Bummer.
>>
>> That rules out this way of doing a conditional conversion.
>>
>> OTOH we can simply make the capturing of the conversion
>> capture its operand if it is not there?
> I am not sure if I understood this.
> eg: (foo (convert?@0 @1))  where foo's any operator.
> gets lowered to:
> a) (foo (convert@0 @1))
> b) (foo @1)

b) (foo @0@1)

that is, both captures capture the same

> in case a), @0 captures (convert @1).
> in case b), when there's no convert, what should @0 capture ?
> It cannot capture foo, (foo@0 @1) since foo's in outermost-expr,
> so should @0 be same as @1 for this case ?

Yes.

>>
>>> d) Use of opt_convert inside for operator-list is rejected.
>>> eg - (for op in convert opt_convert bit_not)
>>>
>>> * Changing syntax:
>>> I was wondering if instead of having new operator like opt_convert, we
>>> could reuse convert ?
>>> convert becomes optional if it's followed with '?'
>>> eg:
>>> (convert? 1 @0) is "optional convert".
>>> or maybe use colon ?
>>> (convert:1 @0) ?
>>> (IMHO '?' is slightly better since it's typically used to denote
>>> "optional" in regexp, but
>>> '? number' looks somewhat out of place in the pattern, ': number' looks better).
>>
>> Hmm, then if we resort to predicate/flag syntax why not do
>> convert:?1 or convert:? convert:?? convert:??? with the number
>> of ?s also providing the match-number.  Of course that makes
>> it look like a generic flag when we should only accept it on converts.
>>
>> Or do convert1?  I don't like the binary form or the number following
>> the ? (looks too much like a capture).  Note that convert1? lexes
>> as one identifier followed by a ? though.
>>
>>> the above pattern becomes:
>>> (plus@2 (convert? 1 (lshift@0 (convert? 2 X) CNT1))
>>>              (convert? 1 (rshift@1 (convert? 2 X) CNT2)))
>>>
>>> "optional" converts won't be allowed to get captured (non-optional convert yes).
>>
>> See above - we should capture its operand if it is not there.
>>
>> So I think let's go with convert1? and allow capturing.  Doing that
>> with appending CONVERT1, CONVERT2, ... to tree.def works for me.
> Thanks, I would do that.
> I was wondering whether it would be okay to change tree.def for this
> purpose though ?
> since convert1, convert2 would be having no other use.

No, not changing tree.def but its use as you did in your first proposed
patch.

Richard.

> Thanks,
> Prathamesh
>>
>> Richard.
>>
>>>
>>> * genmatch.c (enum tree_code): New value OPT_CONVERT.
>>>       (e_operation): New member unsigned group_index.
>>>       (e_operation::e_operation): Add new default argument.
>>>                                               Adjust to changes in e_operation.
>>>       (remove_opt_convert): New function.
>>>       (has_opt_convert): Likewise.
>>>       (lower_opt_convert): Likewise.
>>>       (lower_opt_convert): New overloaded function.
>>>       (lower_opt_convert): Likewise.
>>>       (parse_expr): Adjust to parse opt_convert.
>>>       (parse_for): Reject opt_convert in opers.
>>>       (main): Call lower_opt_convert.
>>>
>>> Thanks,
>>> Prathamesh
>>>>
>>>> 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]