This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: writing patterns
- From: Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: GCC Development <gcc at gcc dot gnu dot org>
- Date: Mon, 4 Aug 2014 20:14:30 +0530
- Subject: Re: writing patterns
- Authentication-results: sourceware.org; auth=none
- References: <CAJXstsDfsQbj4e-RVyGC0grF_UDx5J0pYh=M9H9w=VYA-HBY4w at mail dot gmail dot com> <CAFiYyc0mAyTVrn07+ZSzgRT3of=O90iKkM_HVo1MfTvZaJemvw at mail dot gmail dot com> <CAFiYyc2JyG=jam0XTB3hdyCvmPoN_LFLXW8ca=vcwZnejczj_w at mail dot gmail dot com> <CAJXstsDXyHwQK+dSwyuHPXoDqKv=bceDTL4Yr2Od4YYF6ROXYQ at mail dot gmail dot com> <CAJXstsCfBYf3Z6siL3R6dJ8xrCq6VqJi_c5+uZHVv6QPkLaptQ at mail dot gmail dot com> <CAFiYyc3OC38E2WNpMKfZLGfGLac69QLPJEnbFhLBteOuMPoKwg at mail dot gmail dot com> <CAJXstsAfYKqPwQq58sSaCRPoiMoc9Bs0794qXwvwVvjEG-hdMQ at mail dot gmail dot com> <CAFiYyc2DNWViyx9hK9GkuLzN=9pXLPSXfFwb75w+gvXv12Vr3Q at mail dot gmail dot com> <CAJXstsB4qUdOhfxUtQ5YPzBBtxTBB81nWfQEu0UtXs6BonUohg at mail dot gmail dot com> <CAJXstsB-b37c3VB2VhLXy_6sH=4e9vvP8h8VfeWrE=2Hi1wTyg at mail dot gmail dot com> <CAFiYyc2RxaiCeGD-6GpgSQv9QcjPgdsvk-ww204m+w7C0g-ySQ at mail dot gmail dot com>
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)
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 ?
>
>> 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.
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