[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).
vec
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 and operands: v1[i], v2[j];
append ne to ret;
}
for i = 0 ... v2.length ()
for j = 0 ... v1.length ()
{
ne = new expr with 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 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 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 (o))->where);
+
+ else if (o->type == operand::OP_PREDICATE)
+fprintf (f, "%s", (static_cast (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 (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 (op);
+ operator_id *op_id = static_cast (e->operation->op);
+ enum tree_code code = op_id->code;
+ if (code == PLUS_EXPR || code == MULT_EXPR)
+return true;
+
+ return false;
+}
+
+vec
+commutate (operand *op)
+{
+ vec 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 (op);
+
+ vec v1 = commutate (e->ops[0]);
+ vec 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); // FIXM
Re: [GSoC] commutative patterns
On Fri, Jun 20, 2014 at 2:53 AM, Prathamesh Kulkarni
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).
>
> vec
> 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 and operands: v1[i], v2[j];
> append ne to ret;
> }
>
> for i = 0 ... v2.length ()
> for j = 0 ... v1.length ()
> {
> ne = new expr with 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
> 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
gcc-4.8-20140619 is now available
Snapshot gcc-4.8-20140619 is now available on ftp://gcc.gnu.org/pub/gcc/snapshots/4.8-20140619/ and on various mirrors, see http://gcc.gnu.org/mirrors.html for details. This snapshot has been generated from the GCC 4.8 SVN branch with the following options: svn://gcc.gnu.org/svn/gcc/branches/gcc-4_8-branch revision 211828 You'll find: gcc-4.8-20140619.tar.bz2 Complete GCC MD5=bdb46d0c39714ca1a3f616956c05c7f3 SHA1=1db5302a7f769a36355019de528ebad79a875670 Diffs from 4.8-20140612 are available in the diffs/ subdirectory. When a particular snapshot is ready for public consumption the LATEST-4.8 link is updated and a message is sent to the gcc list. Please do not use a snapshot before it has been announced that way.
Re: regs_used estimation in IVOPTS seriously flawed
On Tue, Jun 17, 2014 at 10:59 PM, Bingfeng Mei wrote:
> Hi,
> I am looking at a performance regression in our code. A big loop produces
> and uses a lot of temporary variables inside the loop body. The problem
> appears that IVOPTS pass creates even more induction variables (from original
> 2 to 27). It causes a lot of register spilling later and performance
Do you have a simplified case which can be posted here? I guess it
affects some other targets too.
> take a severe hit. I looked into tree-ssa-loop-ivopts.c, it does call
> estimate_reg_pressure_cost function to take # of registers into
> consideration. The second parameter passed as data->regs_used is supposed
> to represent old register usage before IVOPTS.
>
> return size + estimate_reg_pressure_cost (size, data->regs_used,
> data->speed,
> data->body_includes_call);
>
> In this case, it is mere 2 by following calculation. Essentially, it only
> counts
> all loop invariant registers, ignoring all registers produced/used inside the
> loop.
There are two kinds of registers produced/used inside the loop. One
is induction variable irrelevant, it includes non-linear uses as
mentioned by Richard. The other kind relates to induction variable
rewrite, and one issue with this kind is expression generated during
iv use rewriting is not reflecting the estimated one in ivopt very
well.
Thanks,
bin
>
> n = 0;
> for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
> {
> phi = gsi_stmt (psi);
> op = PHI_RESULT (phi);
>
> if (virtual_operand_p (op))
> continue;
>
> if (get_iv (data, op))
> continue;
>
> n++;
> }
>
> EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
> {
> struct version_info *info = ver_info (data, j);
>
> if (info->inv_id && info->has_nonlin_use)
> n++;
> }
>
> data->regs_used = n;
>
> I believe how regs_used is calculated is seriously flawed,
> or estimate_reg_pressure_cost is problematic if n_old is
> only supposed to be loop invariant registers. Either way,
> it affects how IVOPTS makes decision and could result in
> worse code. What do you think? Any idea on how to improve
> this?
>
>
> Thanks,
> Bingfeng
>
--
Best Regards.
