This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.

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

# [GSoC] commutative patterns

• From: Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>
• To: Richard Biener <richard dot guenther at gmail dot com>
• Cc: Diego Novillo <dnovillo at google dot com>, gcc <gcc at gcc dot gnu dot org>, Maxim Kuvyrkov <maxim dot kuvyrkov at linaro dot org>
• Date: Fri, 20 Jun 2014 02:53:59 +0530
• Subject: [GSoC] commutative patterns
• Authentication-results: sourceware.org; auth=none

```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: Message Nav: [Date Index] [Subject Index] [Author Index] [Thread Index] [Date Prev] [Date Next] [Thread Prev] [Thread Next]