[GSoC] commutative patterns

[Prathamesh Kulkarni]

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

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: commutative_2.patch
Type: text/x-patch
Size: 6617 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20140621/1e2fb359/attachment.bin>