[GSoC] commutative patterns

[Prathamesh Kulkarni]

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