Re: writing patterns

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

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 ?

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

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

* 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: genmatch.c
===================================================================
--- genmatch.c	(revision 213343)
+++ genmatch.c	(working copy)
@@ -101,6 +101,7 @@ output_line_directive (FILE *f, source_l
 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)   SYM,
 enum tree_code {
 #include "tree.def"
+OPT_CONVERT,
 MAX_TREE_CODES
 };
 #undef DEFTREECODE
@@ -139,7 +140,7 @@ id_base::hash (const value_type *op)
 
 inline int
 id_base::equal (const value_type *op1,
-			const compare_type *op2)
+		const compare_type *op2)
 {
   return (op1->hashval == op2->hashval
 	  && strcmp (op1->id, op2->id) == 0);
@@ -220,9 +221,10 @@ struct predicate : public operand
 };
 
 struct e_operation {
-  e_operation (const char *id, bool is_commutative_ = false, bool add_new_id = true);
+  e_operation (const char *id, bool is_commutative_ = false, bool add_new_id = true, unsigned group_index_ = 0);
   id_base *op;
   bool is_commutative;
+  unsigned group_index;  // for opt_convert
 };
 
 
@@ -290,9 +292,11 @@ is_a_helper <expr *>::test (operand *op)
 }
 
 
-e_operation::e_operation (const char *id, bool is_commutative_, bool add_new_id)
+e_operation::e_operation (const char *id, bool is_commutative_, bool add_new_id, unsigned group_index_)
 {
   is_commutative = is_commutative_;
+  group_index = group_index_;
+
   id_base tem (id_base::CODE, id);
 
   op = operators.find_with_hash (&tem, tem.hashval);
@@ -590,6 +594,115 @@ lower_commutative (simplify *s, vec<simp
     }
 }
 
+operand *
+remove_opt_convert (operand *o, unsigned group_index)
+{
+ if (o->type != operand::OP_EXPR)
+    return o;
+
+  expr *e = static_cast<expr *> (o);
+  
+  if (strcmp (e->operation->op->id, "opt_convert") == 0 && e->operation->group_index == group_index)
+    return remove_opt_convert (e->ops[0], group_index); 
+  
+  expr *ne = new expr (e->operation);
+  
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ne->append_op (remove_opt_convert (e->ops[i], group_index));
+
+  return ne;
+}
+
+operand *
+lower_opt_convert (operand *o, unsigned group_index)
+{
+  if (o->type != operand::OP_EXPR)
+    return o;
+
+  expr *e = static_cast<expr *> (o);
+  expr *ne;
+
+  if (strcmp (e->operation->op->id, "opt_convert") == 0 && e->operation->group_index == group_index)
+    {
+      struct e_operation *operation = new e_operation ("CONVERT_EXPR");
+//      check_operator (operation->op, e->ops.length ());
+      ne = new expr (operation);
+    }
+  else
+    ne = new expr (e->operation);
+
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ne->append_op (lower_opt_convert (e->ops[i], group_index)); 
+
+  return ne;
+}
+
+bool
+has_opt_convert (operand *o)
+{
+  if (!is_a<expr *> (o))
+    return false;
+
+  expr *e = as_a<expr *> (o);
+  
+  if (strcmp (e->operation->op->id, "opt_convert") == 0)
+    return true;
+
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    if (has_opt_convert (e->ops[i]))
+      return true;
+
+  return false;
+}
+
+void
+lower_opt_convert (vec<operand *>& v, operand *o, unsigned group_index)
+{
+  if (has_opt_convert (o))
+    {
+      v.safe_push (lower_opt_convert (o, group_index));
+      v.safe_push (remove_opt_convert (o, group_index));
+    }
+}
+
+vec<operand *>
+lower_opt_convert (operand *o)
+{
+  vec<operand *> v1 = vNULL;
+  vec<operand *> v2; 
+  v1.safe_push (o);
+
+  for (unsigned i = 1; i < 3; ++i)
+    {
+      v2 = vNULL;
+      for (unsigned j = 0; j < v1.length (); ++j)
+	lower_opt_convert (v2, v1[j], i);
+      
+      if (v2 == vNULL)
+	return v1;
+
+      v1 = vNULL;
+      for (unsigned j = 0; j < v2.length (); ++j)
+	v1.safe_push (v2[j]);
+    }
+
+  return v1;
+}    
+
+void
+lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
+{
+  vec<operand *> matchers = lower_opt_convert (s->match);
+  fprintf (stderr, "matchers.length () = %u\n", matchers.length ()); 
+  for (unsigned i = 0; i < matchers.length (); ++i)
+    {
+      simplify *ns = new simplify (s->name, matchers[i], s->match_location,
+				   s->result, s->result_location, s->ifexpr_vec);
+      simplifiers.safe_push (ns);
+    }
+  fprintf (stderr, "simplifiers.length () = %u\n", simplifiers.length ()); 
+}
+
 void
 check_operator (id_base *op, unsigned n_ops, const cpp_token *token = 0)
 {
@@ -1538,7 +1651,7 @@ dt_simplify::gen_generic (FILE *f)
   fprintf (f, "/* simplify %u */\n", pattern_no);
 
   fprintf (f, "{\n");
-  fprintf (f, "tree captures[4] ATTRIBUTE_UNUSED = {};\n");
+  fprintf (f, "tree captures[4] ATTRIBUTE_UNUSED = {};\n"); 
 
   for (unsigned i = 0; i < dt_simplify::capture_max; ++i)
     if (indexes[i])
@@ -1918,6 +2031,13 @@ parse_expr (cpp_reader *r)
   operand *op;
   bool is_commutative = false;
 
+  if (strcmp (e->operation->op->id, "opt_convert") == 0)
+    {
+      op = e;
+      e->operation->group_index = atoi (get_number (r));  
+      goto parse_operands;
+    }
+
   if (token->type == CPP_COLON
       && !(token->flags & PREV_WHITE))
     {
@@ -1942,6 +2062,8 @@ parse_expr (cpp_reader *r)
     op = parse_capture (r, e);
   else
     op = e;
+
+parse_operands:
   do
     {
       const cpp_token *token = peek (r);
@@ -2067,6 +2189,9 @@ parse_match_and_simplify (cpp_reader *r,
   if (match->type != operand::OP_EXPR)
     fatal_at (loc, "expected uncaptured expression");
 
+  // opt_conver in outermost expr must have expression as it's operand
+  // FIXME: put this check later
+
   token = peek (r);
 
   if (token->type != CPP_OPEN_PAREN)
@@ -2112,6 +2237,9 @@ parse_for (cpp_reader *r, source_locatio
       token = peek (r); 
       if (token->type != CPP_NAME)
 	break;
+      if (strcmp ((const char *) NODE_NAME (token->val.node.node), "opt_convert") == 0)
+	fatal_at (token, "opt_convert is not allowed within for");
+
       opers.safe_push (get_ident (r));
     }
 
@@ -2241,9 +2369,11 @@ main(int argc, char **argv)
   add_operator (SYM, # SYM, # TYPE, NARGS);
 #define END_OF_BASE_TREE_CODES
 #include "tree.def"
+add_operator (OPT_CONVERT, "opt_convert", "tcc_unary", 1);
 #undef END_OF_BASE_TREE_CODES
 #undef DEFTREECODE
 
+
   /* Pre-seed builtin functions.
      ???  Cannot use N (name) as that is targetm.emultls.get_address
      for BUILT_IN_EMUTLS_GET_ADDRESS ... */
@@ -2260,9 +2390,13 @@ main(int argc, char **argv)
   for (unsigned i = 0; i < simplifiers.length (); ++i)
     check_no_user_id (simplifiers[i]);
 
-  vec<simplify *> out_simplifiers = vNULL;
+  vec<simplify *> out_simplifiers0 = vNULL;
   for (unsigned i = 0; i < simplifiers.length (); ++i)
-    lower_commutative (simplifiers[i], out_simplifiers);
+    lower_opt_convert (simplifiers[i], out_simplifiers0);
+  
+  vec<simplify *> out_simplifiers = vNULL;
+  for (unsigned i = 0; i < out_simplifiers0.length (); ++i)
+    lower_commutative (out_simplifiers0[i], out_simplifiers);
 
   if (verbose)
     for (unsigned i = 0; i < out_simplifiers.length (); ++i)