On Sun, Jun 22, 2014 at 9:52 PM, Prathamesh Kulkarni
<bilbotheelffri...@gmail.com> wrote:
> On Sun, Jun 22, 2014 at 3:09 AM, Prathamesh Kulkarni
> <bilbotheelffri...@gmail.com> wrote:
>> On Fri, Jun 20, 2014 at 3:02 AM, Prathamesh Kulkarni
>> <bilbotheelffri...@gmail.com> wrote:
>>>
>>> On Fri, Jun 20, 2014 at 2:53 AM, Prathamesh Kulkarni
>>> <bilbotheelffri...@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.
Good, otherwise we really get too many permutes.
> 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).
you need to use v.safe_grow_cleared (n).
> 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.
Sorry for responding so late (but I was on a short vacation), but instead
of building a vector of simplifys at parsing time I'd have simply inserted
the single simplify twice into the decision tree (by just adjusting the
AST traverse order). Easiest would be if the AST walk was
done during the decision tree insert itself as then one could simply
spawn the permutations at the point a commutative node is inserted.
I suppose it's fine to go with the current patch for now.
I've applied the vector growth fix, removed commutated patterns from
match.pd and annotated the remaining with :c. I also slightly
adjusted the parsing to require the : to not have previous whitespace.
2014-06-23 Richard Biener <rguent...@suse.de>
Prathamesh Kulkarni <bilbotheelffri...@gmail.com>
* match.pd: Remove commutated patterns in favor of :c annotations.
* genmatch.c (e_operation): Add is_commutative flag.
(e_operation::e_operation): Adjust.
(simplify): Make match a vector of matches.
(print_operand): New debug function.
(print_matches): Likewise.
(cartesian_product, commutate): New functions implementing
AST commutation.
(write_nary_simplifiers): Adjust to create code for all
commutations.
(parse_expr): Parse ':<flag>' with <flag> being c for
commutative.
(parse_match_and_simplify): Commutate the AST.
(main): Print commutated simplifiers.
> 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
