This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: [GSoC] commutative patterns
- From: Prathamesh Kulkarni <bilbotheelffriend at gmail dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Diego Novillo <dnovillo at google dot com>, gcc <gcc at gcc dot gnu dot org>, Maxim Kuvyrkov <maxim dot kuvyrkov at linaro dot org>
- Date: Fri, 20 Jun 2014 03:02:54 +0530
- Subject: Re: [GSoC] commutative patterns
- Authentication-results: sourceware.org; auth=none
- References: <CAJXstsCmdC9FQPqynTVmV2kBco7vTk4ifUp5TvauZ4FNfWpCUQ at mail dot gmail dot com>
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
> 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