[GSoC] commutative patterns

[Prathamesh Kulkarni]

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:

(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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: commutative_1.patch
Type: text/x-patch
Size: 4893 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20140619/00a39b10/attachment.bin>