Re: [PATCH][RFC] Add gimple_fold

[Diego Novillo]

On Tue, Mar 22, 2011 at 04:59, Richard Guenther  wrote:

> I simply put it in place as a possibility, I currently don't plan
> to implement any GF_KIND_COMPLEX folders (the caller would need to
> re-gimplify them which doesn't sound too useful).  Maybe I should
> simply drop it.

Perhaps.  Not supporting an "everything else" bucket would help us not
fall into the usual trap of having to support too many weird cases.
Though I'm sure we can find other ways of falling into that ;)


>> For instance, if folding ends up producing a complex tree, would it need to 
>> be
>> gimplified?  Maybe we could generate the gimplified statement and return the
>> SSA name on the LHS?  Though I'm not sure I like even this.
>
> Hm, I tried to avoid making the folder rewrite existing or emit new
> stmts - the idea was to make the interface cheap, not allocating GC
> memory for expressions or statements.

Sounds reasonable.  Perhaps this could be done by a wrapper, if needed.


Diego.

Re: [PATCH][RFC] Add gimple_fold

[Richard Guenther]

On Mon, 21 Mar 2011, Diego Novillo wrote:

> On 03/18/2011 10:11 AM, Richard Guenther wrote:
> > 
> > This tries to extend the previously posted CCP folding patch by
> > introducing a generic interface for non-tree-building, GIMPLE SSA
> > aware folding.  The low-level interface for folding regular
> > operations is
> > 
> > /* Fold the expression composed by *CODEP, TYPE and valueized operands
> > *OP0P,
> > *OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
> > SSA names that turn up during statement lookup and producing a result
> > of at most KIND.  The folding result will be stored in the operands.
> > GF_KIND_FAIL is returned if no folding was done.
> > If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
> > stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
> > If GF_KIND_STMT is returned the folding result is stored in *CODEP,
> > *OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
> > operands for a gimple assignment.
> > If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
> > and will be an arbitrarily complex tree.  */
> > 
> > enum gf_kind
> > gimple_fold (enum tree_code *codep, tree type,
> >   tree *op0p, tree *op1p, tree *op2p,
> >   tree (*valueize)(tree), enum gf_kind kind)
> > 
> > which would allow existing gimple-level foldings to build ontop of this
> > (including fold_stmt and friends and the special CCP foldings).
> > 
> > The current implementation is quite lame, just dispatching to fold,
> > but I plan to integrate it with the CCP and fold_stmt foldings before
> > considering to merge it (eventually producing some sort of statistics
> > of what the fold path catches that the gimple path does not).
> > 
> > The low-level interface needs to be amended by one for builtin calls
> > where I'm not sure if it is going to take decomposed operands
> > or just a gimple statement (I think we have at most 3 operands to
> > any builtin we can fold in some way).
> > 
> > This again is just a RFC (even though the patch "works" as far as
> > plugging into the SCCVN binary operation simplification).
> > 
> 
> I like this.  In terms of the interface, what do you think about this always
> returning an SSA name or (may be) the statement that defines it.  Although, if
> this is just the low-level interface, then we can build a wrapper that calls
> it and returns a statement.

Right, my plan was to wrap existing interfaces around this low-level
implementation.

> Some questions and nits below:
> 
> > + enum gf_kind {
> > + GF_KIND_FAIL = 0,
> > + GF_KIND_CONST,
> > + GF_KIND_VAL,
> > + GF_KIND_STMT,
> > + GF_KIND_COMPLEX
> > + };
> 
> These will need documentation.  The values are also sorted by level of
> complexity, right?

Yes.

> Should we not bother with GF_KIND_COMPLEX?  If we are going to return an
> arbitrarily complex tree, we might as well return GF_KIND_FAIL, I think.  Are
> you implementing GF_KIND_COMPLEX as a workaround or is this the expected
> behaviour?

I simply put it in place as a possibility, I currently don't plan
to implement any GF_KIND_COMPLEX folders (the caller would need to
re-gimplify them which doesn't sound too useful).  Maybe I should
simply drop it.

> For instance, if folding ends up producing a complex tree, would it need to be
> gimplified?  Maybe we could generate the gimplified statement and return the
> SSA name on the LHS?  Though I'm not sure I like even this.

Hm, I tried to avoid making the folder rewrite existing or emit new
stmts - the idea was to make the interface cheap, not allocating GC
memory for expressions or statements.

Thanks,
Richard.

> > +
> > +
> > + static tree
> > + build_valueized_tree_from_def (tree name, tree (*valueize)(tree))
> > + {
> 
> Needs comment.
> 
> > +   gimple def_stmt = SSA_NAME_DEF_STMT (name);
> > +   tree op0, op1, op2;
> > +
> > +   if (!is_gimple_assign (def_stmt)
> > +   || gimple_vuse (def_stmt))
> > + return name;
> > +
> > +   switch (gimple_assign_rhs_class (def_stmt))
> > + {
> > + case GIMPLE_SINGLE_RHS:
> > +   return gimple_assign_rhs1 (def_stmt);
> > +
> > + case GIMPLE_TERNARY_RHS:
> > +   op2 = gimple_assign_rhs3 (def_stmt);
> > +   if (TREE_CODE (op2) == SSA_NAME
> > +   &&  valueize)
> > +   op2 = (*valueize) (op2);
> > +
> > + case GIMPLE_BINARY_RHS:
> > +   op1 = gimple_assign_rhs2 (def_stmt);
> > +   if (TREE_CODE (op1) == SSA_NAME
> > +   &&  valueize)
> > +   op1 = (*valueize) (op1);
> > +
> 
> /* Fallthru  */
> 
> > + case GIMPLE_UNARY_RHS:
> > +   op0 = gimple_assign_rhs1 (def_stmt);
> > +   if (TREE_CODE (op0) == SSA_NAME
> > +   &&  valueize)
> > +   op0 = (*valueize) (op0);
> > +   break;
> > +
> > + default:;
> > + }
> > +
> > +   switch (gimple_assign_rhs_class (def_stmt))
> > + {
> > + case GIMPLE_UNARY_RHS:
> > +   return fold_build1 (gimple_ass

Re: [PATCH][RFC] Add gimple_fold

[Diego Novillo]

On 03/18/2011 10:11 AM, Richard Guenther wrote:


This tries to extend the previously posted CCP folding patch by
introducing a generic interface for non-tree-building, GIMPLE SSA
aware folding.  The low-level interface for folding regular
operations is

/* Fold the expression composed by *CODEP, TYPE and valueized operands
*OP0P,
*OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
SSA names that turn up during statement lookup and producing a result
of at most KIND.  The folding result will be stored in the operands.
GF_KIND_FAIL is returned if no folding was done.
If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
If GF_KIND_STMT is returned the folding result is stored in *CODEP,
*OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
operands for a gimple assignment.
If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
and will be an arbitrarily complex tree.  */

enum gf_kind
gimple_fold (enum tree_code *codep, tree type,
  tree *op0p, tree *op1p, tree *op2p,
  tree (*valueize)(tree), enum gf_kind kind)

which would allow existing gimple-level foldings to build ontop of this
(including fold_stmt and friends and the special CCP foldings).

The current implementation is quite lame, just dispatching to fold,
but I plan to integrate it with the CCP and fold_stmt foldings before
considering to merge it (eventually producing some sort of statistics
of what the fold path catches that the gimple path does not).

The low-level interface needs to be amended by one for builtin calls
where I'm not sure if it is going to take decomposed operands
or just a gimple statement (I think we have at most 3 operands to
any builtin we can fold in some way).

This again is just a RFC (even though the patch "works" as far as
plugging into the SCCVN binary operation simplification).



I like this.  In terms of the interface, what do you think about this 
always returning an SSA name or (may be) the statement that defines it. 
 Although, if this is just the low-level interface, then we can build a 
wrapper that calls it and returns a statement.


Some questions and nits below:


+ enum gf_kind {
+ GF_KIND_FAIL = 0,
+ GF_KIND_CONST,
+ GF_KIND_VAL,
+ GF_KIND_STMT,
+ GF_KIND_COMPLEX
+ };


These will need documentation.  The values are also sorted by level of 
complexity, right?


Should we not bother with GF_KIND_COMPLEX?  If we are going to return an 
arbitrarily complex tree, we might as well return GF_KIND_FAIL, I think. 
 Are you implementing GF_KIND_COMPLEX as a workaround or is this the 
expected behaviour?


For instance, if folding ends up producing a complex tree, would it need 
to be gimplified?  Maybe we could generate the gimplified statement and 
return the SSA name on the LHS?  Though I'm not sure I like even this.



+
+
+ static tree
+ build_valueized_tree_from_def (tree name, tree (*valueize)(tree))
+ {


Needs comment.


+   gimple def_stmt = SSA_NAME_DEF_STMT (name);
+   tree op0, op1, op2;
+
+   if (!is_gimple_assign (def_stmt)
+   || gimple_vuse (def_stmt))
+ return name;
+
+   switch (gimple_assign_rhs_class (def_stmt))
+ {
+ case GIMPLE_SINGLE_RHS:
+   return gimple_assign_rhs1 (def_stmt);
+
+ case GIMPLE_TERNARY_RHS:
+   op2 = gimple_assign_rhs3 (def_stmt);
+   if (TREE_CODE (op2) == SSA_NAME
+   &&  valueize)
+   op2 = (*valueize) (op2);
+
+ case GIMPLE_BINARY_RHS:
+   op1 = gimple_assign_rhs2 (def_stmt);
+   if (TREE_CODE (op1) == SSA_NAME
+   &&  valueize)
+   op1 = (*valueize) (op1);
+


/* Fallthru  */


+ case GIMPLE_UNARY_RHS:
+   op0 = gimple_assign_rhs1 (def_stmt);
+   if (TREE_CODE (op0) == SSA_NAME
+   &&  valueize)
+   op0 = (*valueize) (op0);
+   break;
+
+ default:;
+ }
+
+   switch (gimple_assign_rhs_class (def_stmt))
+ {
+ case GIMPLE_UNARY_RHS:
+   return fold_build1 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0);
+ case GIMPLE_BINARY_RHS:
+   return fold_build2 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0, op1);
+ case GIMPLE_TERNARY_RHS:
+   return fold_build3 (gimple_assign_rhs_code (def_stmt),
+ TREE_TYPE (name), op0, op1, op2);
+ default:;
+ }
+
+   return name;
+ }
+
+ static enum gf_kind
+ const_or_val (tree res, enum gf_kind kind)
+ {


Needs comment.


Diego.

[PATCH][RFC] Add gimple_fold

[Richard Guenther]

This tries to extend the previously posted CCP folding patch by
introducing a generic interface for non-tree-building, GIMPLE SSA
aware folding.  The low-level interface for folding regular
operations is

/* Fold the expression composed by *CODEP, TYPE and valueized operands 
*OP0P,
   *OP1P and *OP2P (as required), using the VALUEIZE callback to valueize
   SSA names that turn up during statement lookup and producing a result
   of at most KIND.  The folding result will be stored in the operands.
   GF_KIND_FAIL is returned if no folding was done.
   If GF_KIND_CONST or GF_KIND_VAL is returned the folding result is
   stored in *OP0P and is a is_gimple_min_invariant or a is_gimple_val.
   If GF_KIND_STMT is returned the folding result is stored in *CODEP,
   *OP0P, *OP1P and *OP2P (as required) and will compose a valid set of
   operands for a gimple assignment.
   If GF_KIND_COMPLEX is returned the folding result is stored in *OP0P
   and will be an arbitrarily complex tree.  */

enum gf_kind
gimple_fold (enum tree_code *codep, tree type,
 tree *op0p, tree *op1p, tree *op2p,
 tree (*valueize)(tree), enum gf_kind kind)

which would allow existing gimple-level foldings to build ontop of this
(including fold_stmt and friends and the special CCP foldings).

The current implementation is quite lame, just dispatching to fold,
but I plan to integrate it with the CCP and fold_stmt foldings before
considering to merge it (eventually producing some sort of statistics
of what the fold path catches that the gimple path does not).

The low-level interface needs to be amended by one for builtin calls
where I'm not sure if it is going to take decomposed operands
or just a gimple statement (I think we have at most 3 operands to
any builtin we can fold in some way).

This again is just a RFC (even though the patch "works" as far as
plugging into the SCCVN binary operation simplification).

Thanks,
Richard.



Index: gcc/gimple-fold.h
===
*** gcc/gimple-fold.h   (revision 0)
--- gcc/gimple-fold.h   (revision 0)
***
*** 0 
--- 1,39 
+ /* Gimple folding definitions.
+ 
+Copyright 2011 Free Software Foundation, Inc.
+Contributed by Richard Guenther 
+ 
+ This file is part of GCC.
+ 
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3, or (at your option) any later
+ version.
+ 
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3.  If not see
+ .  */
+ 
+ #ifndef GCC_GIMPLE_FOLD_H
+ #define GCC_GIMPLE_FOLD_H
+ 
+ #include "coretypes.h"
+ 
+ enum gf_kind {
+ GF_KIND_FAIL = 0,
+ GF_KIND_CONST,
+ GF_KIND_VAL,
+ GF_KIND_STMT,
+ GF_KIND_COMPLEX
+ };
+ 
+ enum gf_kind gimple_fold (enum tree_code *, tree,
+ tree *, tree *, tree *,
+ tree (*)(tree), enum gf_kind);
+ 
+ #endif  /* GCC_GIMPLE_FOLD_H */
Index: gcc/gimple-fold.c
===
*** gcc/gimple-fold.c   (revision 171133)
--- gcc/gimple-fold.c   (working copy)
*** along with GCC; see the file COPYING3.
*** 30,35 
--- 30,36 
  #include "tree-pass.h"
  #include "tree-ssa-propagate.h"
  #include "target.h"
+ #include "gimple-fold.h"
  
  /* Return true when DECL can be referenced from current unit.
 We can get declarations that are not possible to reference for
*** maybe_fold_or_comparisons (enum tree_cod
*** 2665,2667 
--- 2666,2914 
else
  return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
  }
+ 
+ 
+ static tree
+ build_valueized_tree_from_def (tree name, tree (*valueize)(tree))
+ {
+   gimple def_stmt = SSA_NAME_DEF_STMT (name);
+   tree op0, op1, op2;
+ 
+   if (!is_gimple_assign (def_stmt)
+   || gimple_vuse (def_stmt))
+ return name;
+ 
+   switch (gimple_assign_rhs_class (def_stmt))
+ {
+ case GIMPLE_SINGLE_RHS:
+   return gimple_assign_rhs1 (def_stmt);
+ 
+ case GIMPLE_TERNARY_RHS:
+   op2 = gimple_assign_rhs3 (def_stmt);
+   if (TREE_CODE (op2) == SSA_NAME
+ && valueize)
+   op2 = (*valueize) (op2);
+ 
+ case GIMPLE_BINARY_RHS:
+   op1 = gimple_assign_rhs2 (def_stmt);
+   if (TREE_CODE (op1) == SSA_NAME
+ && valueize)
+   op1 = (*valueize) (op1);
+ 
+ case GIMPLE_UNARY_RHS:
+   op0 = gimple_assign_rhs1 (def_stmt);
+   if (TREE_CODE (op0) == SSA_NAME
+ && valueize)
+   op0 = (*valueize) (op0);
+   break;
+ 
+ default:;
+ }
+