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