On Mon, Aug 4, 2014 at 2:59 PM, Richard Biener <richard.guent...@gmail.com> wrote: > On Mon, Aug 4, 2014 at 12:16 AM, Prathamesh Kulkarni > <bilbotheelffri...@gmail.com> wrote: >> On Thu, Jul 31, 2014 at 2:49 PM, Prathamesh Kulkarni >> <bilbotheelffri...@gmail.com> wrote: >>> On Thu, Jul 31, 2014 at 2:44 PM, Richard Biener >>> <richard.guent...@gmail.com> wrote: >>>> On Thu, Jul 31, 2014 at 11:09 AM, Prathamesh Kulkarni >>>> <bilbotheelffri...@gmail.com> wrote: >>>>> On Thu, Jul 31, 2014 at 2:15 PM, Richard Biener >>>>> <richard.guent...@gmail.com> wrote: >>>>>> On Thu, Jul 31, 2014 at 7:41 AM, Prathamesh Kulkarni >>>>>> <bilbotheelffri...@gmail.com> wrote: >>>>>>> On Wed, Jul 30, 2014 at 11:49 PM, Prathamesh Kulkarni >>>>>>> <bilbotheelffri...@gmail.com> wrote: >>>>>>>> On Wed, Jul 30, 2014 at 4:49 PM, Richard Biener >>>>>>>> <richard.guent...@gmail.com> wrote: >>>>>>>>> On Wed, Jul 30, 2014 at 1:11 PM, Richard Biener >>>>>>>>> <richard.guent...@gmail.com> wrote: >>>>>>>>>> On Wed, Jul 30, 2014 at 12:49 PM, Prathamesh Kulkarni >>>>>>>>>> <bilbotheelffri...@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
