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]

[GSoC] commutative patterns


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:

(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.
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: gcc/genmatch.c
===================================================================
--- gcc/genmatch.c	(revision 211732)
+++ gcc/genmatch.c	(working copy)
@@ -293,14 +293,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 +308,108 @@ struct simplify {
   source_location result_location;
 };
 
+void
+print_operand (operand *o, FILE *f = stderr) 
+{
+  if (o->type == operand::OP_CAPTURE)
+    fprintf (f, "@%s", (static_cast<capture *> (o))->where);
+
+  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);
+    }
+}
+
+bool
+is_commutative (operand *op)
+{
+  if (op->type != operand::OP_EXPR)
+    return false;
+
+  expr *e = static_cast<expr *> (op);
+  operator_id *op_id = static_cast <operator_id *> (e->operation->op);
+  enum tree_code code = op_id->code;
 
+  if (code == PLUS_EXPR || code == MULT_EXPR)
+    return true;
+
+  return false;
+}
+
+vec<operand *>
+commutate (operand *op)
+{
+  vec<operand *> ret = vNULL;
+
+  if (!is_commutative (op))
+    {
+      ret.safe_push (op);  // FIXME: should we clone op ? ret.safe_push (op->clone()) 
+      return ret;
+    }
+
+  expr *e = static_cast<expr *> (op);
+
+  vec<operand *> v1 = commutate (e->ops[0]);
+  vec<operand *> v2 = commutate (e->ops[1]);
+
+  unsigned i, j;
+
+  for (i = 0; i < v1.length (); ++i)
+    for (j = 0; j < v2.length (); ++j)
+      {
+	expr *ne = new expr (e->operation);  // FIXME: e->operation should be cloned ?
+	ne->append_op (v1[i]);
+	ne->append_op (v2[j]);
+	ret.safe_push (ne);
+      }
+
+  for (i = 0; i < v2.length (); ++i)
+    for (j = 0; j < v1.length (); ++j)
+      {
+	expr *ne = new expr (e->operation);
+	ne->append_op (v2[i]);
+	ne->append_op (v1[j]);
+	ret.safe_push (ne);
+      }
+
+  return ret;
+}
 
 /* Code gen off the AST.  */
 
@@ -574,11 +675,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 +735,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");
 }
@@ -971,7 +1080,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 +1152,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);

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]