Re: [GSoC] commutative patterns

[Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>]

On Sun, Jun 22, 2014 at 3:09 AM, Prathamesh Kulkarni
<bilbotheelffriend@gmail.com> wrote:
> On Fri, Jun 20, 2014 at 3:02 AM, Prathamesh Kulkarni
> <bilbotheelffriend@gmail.com> wrote:
>>
>> On Fri, Jun 20, 2014 at 2:53 AM, Prathamesh Kulkarni
>> <bilbotheelffriend@gmail.com> wrote:
>> > Hi,
>> >     The attached patch attempts to generate commutative variants for
>> > a given expression.
>> >
>> > Example:
>> > For the AST: (PLUS_EXPR (PLUS_EXPR @0 @1) @2),
>> >
>> > the commutative variants are:
>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) @2 )
>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) @2 )
>> > (PLUS_EXPR @2 (PLUS_EXPR @0 @1 ) )
>> > (PLUS_EXPR @2 (PLUS_EXPR @1 @0 ) )
>> >
>> >
>> > * Basic Idea:
>> > Consider expression e with two operands o0, and o1,
>> > and expr-code denoting expression's code (plus/mult, etc.)
>> >
>> > Commutative variants are stored in vector (vec<operand *>).
>> >
>> > vec<operand *>
>> > commutative (e)
>> > {
>> >   if (e is not commutative)
>> >     return [e];  // vector with only one expression
>> >
>> >   v1 = commutative (o0);
>> >   v2 = commutative (o1);
>> >   ret = []
>> >
>> >   for i = 0 ... v1.length ()
>> >     for j = 0 ... v2.length ()
>> >       {
>> >         ne = new expr with <expr-code> and operands: v1[i], v2[j];
>> >         append ne to ret;
>> >       }
>> >
>> >   for i = 0 ... v2.length ()
>> >     for j = 0 ... v1.length ()
>> >       {
>> >         ne = new expr with <expr-code> and operand: v2[i], v1[j];
>> >         append ne to ret
>> >       }
>> >
>> >   return ret;
>> > }
>> >
>> > Example:
>> > (plus (plus @0 @1) (plus @2 @3))
>> > generates following commutative variants:
>> oops.
>> the pattern given to genmatch was (bogus):
>> (plus (plus @0 @1) (plus @0 @3))
>> >
>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) (PLUS_EXPR @0 @3 ) )
>> > (PLUS_EXPR (PLUS_EXPR @0 @1 ) (PLUS_EXPR @3 @0 ) )
>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) (PLUS_EXPR @0 @3 ) )
>> > (PLUS_EXPR (PLUS_EXPR @1 @0 ) (PLUS_EXPR @3 @0 ) )
>> > (PLUS_EXPR (PLUS_EXPR @0 @3 ) (PLUS_EXPR @0 @1 ) )
>> > (PLUS_EXPR (PLUS_EXPR @0 @3 ) (PLUS_EXPR @1 @0 ) )
>> > (PLUS_EXPR (PLUS_EXPR @3 @0 ) (PLUS_EXPR @0 @1 ) )
>> > (PLUS_EXPR (PLUS_EXPR @3 @0 ) (PLUS_EXPR @1 @0 ) )
>> >
>> >
>> > * Decide which operators are commutative.
>> > Currently I assume all PLUS_EXPR and MULT_EXPR are true.
>> s/true/commutative
> There's a bug in the previous patch - if the operator is not
> commutative, it does not try
> for generating commutative variants of it's operands, and does not
> commutate captured
> expression (.what).
> example:
> (negate (plus @0 @1)) has two commutative variants (including the
> original pattern),
> but the patch does not generate them, since negate is not commutative.
>
> The attached patch fixes that. As a quick hack i handled each operator
> class (unary, binary, ternary)
> specially (commutate_unary, commutate_binary, commutate_ternary).
> Ideally it should be unified
> (I tried that way, but it was segfaulting). I will try and come up
> with a better way.
> Also the current patch won't work for built-in functions/operators
> having more than 3 operands.
> (max we have 3 so far in match.pd for cond, I hope this doesn't come
> "in the way").
>
> With the current patch,
> for the expression (negate (plus @0 @1))
> it generates following commutative variants:
> (negate (plus @0 @1))
> (negate (plus @1 @0))
>
> and for the following pattern (involving captured expression):
> (negate (plus@0 @1 @2))
> it generates following variants:
> (negate (plus@0 @1 @2))
> (negate (plus@0 @2 @1))
>
> * generates multiple matching patterns
> Since at AST-level we do not test for captures equality (true/match),
> it treats both of the captures
> as different, even though they are same.
> example: the following also expression has 2 variants generated
> (BUILT_IN_SQRT (mult @0 @0))
> commutative variants:
> (BUILT_IN_SQRT (mult @0 @0))
> (BUILT_IN_SQRT (mult @0 @0))
> I guess this won't really be a problem with decision tree. If we decide to emit
> warning, we should warn only for user defined patterns, and not generated ones.
>
> * syntax for commutative operators
> Currently, I assume any PLUS_EXPR / MULT_EXPR to be commutative.
> I guess we should have syntax for users marking an operator to be commutative.
>
> sth like:
> a) op:c
> b) op "c"
> c) op!
> d) op "commutative"
>
> Or any other, that you would like -:)
>
> * cloning AST nodes
> Currently I do not do a deep-copy of the AST for each distinct
> commutative variant, so the nodes
> are shared for different expressions, which are commutative variants
> of the original expression.
> Is this OK, or should we clone each AST node, so that each expression
> is represented by a distinct AST ?
> cloning shall eat up space, while sharing shall require more careful
> memory management (freeing one ast, may also
> free nodes of other expression).
This patch removes the hack of special handling according to operator classes.
For now, I added op:c syntax to denote operator op as commutative.

Example: (does not commutate outer plus since it's not marked commutative).
(plus (plus:c@0 @1 @2))
generates following variants:
(PLUS_EXPR (PLUS_EXPR@0 @1 @2 )  @3 )
(PLUS_EXPR (PLUS_EXPR@0 @2 @1 )  @3 )

How do we resize a vector to hold n elements at start ?
I tried:
vec<operand *> v = vNULL;
v.resize (n);
v.resize_exact (n);
however accessing v[i] led to internal abort in operator[] (vec.h line 735).

As a work-around I did (in cartesian_product):
for (unsigned i = 0; i < n_ops; ++i)
  v.safe_push (0);
This works to make vector "big enough" to hold n_ops elements, but is
rather ugly.

Thanks and Regards,
Prathamesh
>
> Thanks and Regards,
> Prathamesh
>
>> > Maybe we should add syntax to mark a particular operator as commutative ?
>> >
>> > * Cloning AST nodes
>> > While creating another AST that represents one of
>> > the commutative variants, should we clone the AST nodes,
>> > so that all commutative variants have distinct AST nodes ?
>> > That's not done currently, and AST nodes are shared amongst
>> > different commutative expressions, and we end up with a DAG,
>> > for a set of commutative expressions.
>> >
>> > Thanks and Regards,
>> > Prathamesh

Index: genmatch.c
===================================================================
--- genmatch.c	(revision 211732)
+++ genmatch.c	(working copy)
@@ -119,7 +119,7 @@ struct id_base : typed_free_remove<id_ba
 {
   enum id_kind { CODE, FN } kind;
 
-  id_base (id_kind, const char *);
+  id_base (id_kind, const char *); 
 
   hashval_t hashval;
   const char *id;
@@ -146,7 +146,7 @@ id_base::equal (const value_type *op1,
 
 static hash_table<id_base> operators;
 
-id_base::id_base (id_kind kind_, const char *id_)
+id_base::id_base (id_kind kind_, const char *id_) 
 {
   kind = kind_;
   id = id_;
@@ -218,8 +218,9 @@ struct predicate : public operand
 };
 
 struct e_operation {
-  e_operation (const char *id);
+  e_operation (const char *id, bool is_commutative_ = false);
   id_base *op;
+  bool is_commutative;
 };
 
 
@@ -258,9 +259,11 @@ struct capture : public operand
 };
 
 
-e_operation::e_operation (const char *id)
+e_operation::e_operation (const char *id, bool is_commutative_)
 {
   id_base tem (id_base::CODE, id);
+  is_commutative = is_commutative_;
+
   op = operators.find_with_hash (&tem, tem.hashval);
   if (op)
     return;
@@ -293,14 +296,14 @@ e_operation::e_operation (const char *id
 
 struct simplify {
   simplify (const char *name_,
-	    struct operand *match_, source_location match_location_,
+	    vec<operand *> matchers_, source_location match_location_,
 	    struct operand *ifexpr_, source_location ifexpr_location_,
 	    struct operand *result_, source_location result_location_)
-      : name (name_), match (match_), match_location (match_location_),
+      : name (name_), matchers (matchers_), match_location (match_location_),
       ifexpr (ifexpr_), ifexpr_location (ifexpr_location_),
       result (result_), result_location (result_location_) {}
   const char *name;
-  struct operand *match;
+  vec<operand *> matchers;  // vector to hold commutative expressions
   source_location match_location;
   struct operand *ifexpr;
   source_location ifexpr_location;
@@ -308,7 +311,148 @@ struct simplify {
   source_location result_location;
 };
 
+void
+print_operand (operand *o, FILE *f = stderr)
+{
+  if (o->type == operand::OP_CAPTURE)
+    {
+      capture *c = static_cast<capture *> (o);
+      fprintf (f, "@%s", (static_cast<capture *> (o))->where);
+      if (c->what)
+	{
+	  putc (':', f);
+	  print_operand (c->what, f);
+	  putc (' ', f);
+	}
+    }
+
+  else if (o->type == operand::OP_PREDICATE)
+    fprintf (f, "%s", (static_cast<predicate *> (o))->ident);
+
+  else if (o->type == operand::OP_C_EXPR)
+    fprintf (f, "c_expr");
+
+  else if (o->type == operand::OP_EXPR)
+    {
+      expr *e = static_cast<expr *> (o);
+      fprintf (f, "(%s ", e->operation->op->id);
+
+      for (unsigned i = 0; i < e->ops.length (); ++i)
+	{
+	  print_operand (e->ops[i], f);
+	  putc (' ', f);
+	}
+
+      putc (')', f);
+    }
+
+  else
+    gcc_unreachable ();
+}
+
+void
+print_matches (struct simplify *s, FILE *f = stderr)
+{
+  if (s->matchers.length () == 1)
+    return;
+
+  fprintf (f, "for expression: ");
+  print_operand (s->matchers[0], f);  // s->matchers[0] is equivalent to original expression
+  putc ('\n', f);
+
+  fprintf (f, "commutative expressions:\n");
+  for (unsigned i = 0; i < s->matchers.length (); ++i)
+    {
+      print_operand (s->matchers[i], f);
+      putc ('\n', f);
+    }
+}
+
+void
+cartesian_product (const vec< vec<operand *> >& ops_vector, vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
+{
+  if (n == ops_vector.length ())
+    {
+      vec<operand *> xv = v.copy (); 
+      result.safe_push (xv);
+      return;
+    }
+
+  for (unsigned i = 0; i < ops_vector[n].length (); ++i)
+    {
+      v[n] = ops_vector[n][i];
+      cartesian_product (ops_vector, result, v, n + 1);
+    }
+}
+ 
+void
+cartesian_product (const vec< vec<operand *> >& ops_vector, vec< vec<operand *> >& result, unsigned n_ops)
+{
+  vec<operand *> v = vNULL;
+// FIXME: this is done to resize v to length n_ops.
+  for (unsigned i = 0; i < n_ops; ++i)
+    v.safe_push (0);
+  cartesian_product (ops_vector, result, v, 0);
+}
+
+vec<operand *>
+commutate (operand *op)
+{
+  vec<operand *> ret = vNULL;
+
+  if (op->type == operand::OP_CAPTURE)
+    {
+      capture *c = static_cast<capture *> (op);
+      if (!c->what)
+	{
+	  ret.safe_push (op);
+	  return ret;
+	}
+      vec<operand *> v = commutate (c->what);
+      for (unsigned i = 0; i < v.length (); ++i)
+	{
+	  capture *nc = new capture (c->where, v[i]);
+	  ret.safe_push (nc);
+	}
+      return ret;	
+    }
+
+  if (op->type != operand::OP_EXPR)
+    {
+      ret.safe_push (op);
+      return ret;
+    }
+
+  expr *e = static_cast<expr *> (op);
+
+  vec< vec<operand *> > ops_vector = vNULL;
+  for (unsigned i = 0; i < e->ops.length (); ++i)
+    ops_vector.safe_push (commutate (e->ops[i]));
+
+  vec< vec<operand *> > result = vNULL;
+  cartesian_product (ops_vector, result, e->ops.length ());
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      for (unsigned j = 0; j < result[i].length (); ++j)
+	ne->append_op (result[i][j]);
+      ret.safe_push (ne);
+    }
 
+  if (!e->operation->is_commutative)
+    return ret;
+
+  for (unsigned i = 0; i < result.length (); ++i)
+    {
+      expr *ne = new expr (e->operation);
+      for (unsigned j = result[i].length (); j; --j)  // result[i].length () is 2 since e->operation is binary
+	ne->append_op (result[i][j-1]);
+      ret.safe_push (ne);
+    }
+
+  return ret;
+}
 
 /* Code gen off the AST.  */
 
@@ -574,11 +718,15 @@ write_nary_simplifiers (FILE *f, vec<sim
     {
       simplify *s = simplifiers[i];
       /* ???  This means we can't capture the outermost expression.  */
-      if (s->match->type != operand::OP_EXPR)
+      for (unsigned i = 0; i < s->matchers.length (); ++i)
+	{
+	  operand *match = s->matchers[i];
+	  if (match->type != operand::OP_EXPR)
 	continue;
-      expr *e = static_cast <expr *> (s->match);
+	  expr *e = static_cast <expr *> (match);
       if (e->ops.length () != n)
 	continue;
+
       char fail_label[16];
       snprintf (fail_label, 16, "fail%d", label_cnt++);
       output_line_directive (f, s->match_location);
@@ -627,6 +775,7 @@ write_nary_simplifiers (FILE *f, vec<sim
       fprintf (f, "    }\n");
       fprintf (f, "%s:\n", fail_label);
     }
+    }
   fprintf (f, "  return false;\n");
   fprintf (f, "}\n");
 }
@@ -827,6 +976,25 @@ parse_expr (cpp_reader *r)
   expr *e = new expr (parse_operation (r));
   const cpp_token *token = peek (r);
   operand *op;
+  bool is_commutative = false;
+
+  if (token->type == CPP_COLON)
+    {
+      eat_token (r, CPP_COLON);
+      token = peek (r);
+      if (token->type == CPP_NAME
+	  && !(token->flags & PREV_WHITE))
+	{
+	  const char *s = (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
+	  eat_token (r, CPP_NAME);
+	  token = peek (r);
+	  if (s[0] == 'c' && !s[1])
+	    is_commutative = true;
+	  else
+	    fatal_at (token, "not implemented: predicates on expressions");
+	}
+    }
+
   if (token->type == CPP_ATSIGN
       && !(token->flags & PREV_WHITE))
     op = parse_capture (r, e);
@@ -847,6 +1015,13 @@ parse_expr (cpp_reader *r)
 		fatal_at (token, "got %d operands instead of the required %d",
 			  e->ops.length (), opr->get_required_nargs ());
 	    }
+	  if (is_commutative)
+	    {
+	      if (e->ops.length () == 2)
+		e->operation->is_commutative = true;
+	      else
+		fatal_at (token, "only binary operators or function with two arguments can be marked commutative");
+	    }
 	  return op;
 	}
       e->append_op (parse_op (r));
@@ -971,7 +1146,7 @@ parse_match_and_simplify (cpp_reader *r,
       ifexpr = parse_c_expr (r, CPP_OPEN_PAREN);
     }
   token = peek (r);
-  return new simplify (id, match, match_location,
+  return new simplify (id, commutate (match), match_location,
 		       ifexpr, ifexpr_location, parse_op (r), token->src_loc);
 }
 
@@ -1043,6 +1218,9 @@ main(int argc, char **argv)
     }
   while (1);
 
+  for (unsigned i = 0; i < simplifiers.length (); ++i)
+    print_matches (simplifiers[i]);
+
   write_gimple (stdout, simplifiers);
 
   cpp_finish (r, NULL);