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 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 ...

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).

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]