RFC: Gimple combine/folding interface

RFC: Gimple combine/folding interface

[Andrew Pinski]

I was creating a new gimple/folding interface and wanted some opinions
on the interface.

typedef double_int (*nonzerobits_t)(tree var);
typedef tree (*valueizer_t)(tree var);

class gimple_combine
{
public:
  gimple_combine(nonzerobits_t a, valueizer_t b) : nonzerobitsf(a),
valueizerv(b), allow_full_reassiocation(false) {}
  gimple_combine() : nonzerobitsf(NULL), valueizerv(NULL),
allow_full_reassiocation(false) {}
  gimple_combine(bool reas) : nonzerobitsf(NULL), valueizerv(NULL),
allow_full_reassiocation(reas) {}
  tree build2 (location_t, enum tree_code, tree, tree, tree);
  tree build1 (location_t, enum tree_code, tree, tree);
  tree build3 (location_t, enum tree_code, tree, tree, tree, tree);
  tree combine (gimple);
private:
  nonzerobits_t nonzerobitsf;
  valueizer_t valueizerv;
  bool allow_full_reassiocation;
  tree binary (location_t, enum tree_code, tree, tree, tree);
  tree unary (location_t, enum tree_code, tree, tree);
  tree ternary (location_t, enum tree_code, tree, tree, tree, tree);
};

bool replace_rhs_after_ssa_combine (gimple_stmt_iterator *, tree);

This is what I have so far and wonder if there is anything else I
should include.

This will be used to replace the folding code in fold-const.c and gimple-fold.c.

Thanks,
Andrew Pinski

Re: RFC: Gimple combine/folding interface

[Marc Glisse]

On Fri, 19 Jul 2013, Andrew Pinski wrote:

> I was creating a new gimple/folding interface

Thanks.

> and wanted some opinions on the interface.
>
> typedef double_int (*nonzerobits_t)(tree var);
> typedef tree (*valueizer_t)(tree var);
>
> class gimple_combine
> {
> public:
>  gimple_combine(nonzerobits_t a, valueizer_t b) : nonzerobitsf(a),
> valueizerv(b), allow_full_reassiocation(false) {}
>  gimple_combine() : nonzerobitsf(NULL), valueizerv(NULL),
> allow_full_reassiocation(false) {}
>  gimple_combine(bool reas) : nonzerobitsf(NULL), valueizerv(NULL),
> allow_full_reassiocation(reas) {}
>  tree build2 (location_t, enum tree_code, tree, tree, tree);
>  tree build1 (location_t, enum tree_code, tree, tree);
>  tree build3 (location_t, enum tree_code, tree, tree, tree, tree);
>  tree combine (gimple);
> private:
>  nonzerobits_t nonzerobitsf;
>  valueizer_t valueizerv;
>  bool allow_full_reassiocation;
>  tree binary (location_t, enum tree_code, tree, tree, tree);
>  tree unary (location_t, enum tree_code, tree, tree);
>  tree ternary (location_t, enum tree_code, tree, tree, tree, tree);
> };
>
> bool replace_rhs_after_ssa_combine (gimple_stmt_iterator *, tree);
>
> This is what I have so far and wonder if there is anything else I
> should include.
>
> This will be used to replace the folding code in fold-const.c and 
> gimple-fold.c.

And half of tree-ssa-forwprop.c ?

replace_rhs_after_ssa_combine:
- does "after" mean it is somehow delayed, or just that it is meant to be 
called right after combine?
- is the return value an indication that some cleanup is needed?
- does it re-gimplify its argument if it isn't a valid gimple rhs?

Would the valueizer be limited to single use variables? Depending on the 
transformation, we may want to restrict to single use or not.

It would be possible to use a single name instead of build1, build2, 
build3 (either with overloading or with default argument values).

Not sure it should be called gimple_combine since with a trivial valueizer 
it would be a generic tree folder (maybe the combine function could be 
overloaded so it can take a tree and replace fold?).

It may be convenient to forbid valueizerv==0 and use instead a trivial one 
that just returns its argument, so we don't have to test if valueizer 
exists everytime we use it.

With this interface, we will build trees and immediatly convert them to 
gimple and forget them. That doesn't seem easy to avoid...

No folding categories as in 
http://gcc.gnu.org/ml/gcc-patches/2011-03/msg01099.html ?

-- 
Marc Glisse

Re: RFC: Gimple combine/folding interface

[Andrew Pinski]

On Fri, Jul 19, 2013 at 5:09 PM, Andrew Pinski <pinskia@gmail.com> wrote:
> I was creating a new gimple/folding interface and wanted some opinions
> on the interface.
>
> typedef double_int (*nonzerobits_t)(tree var);
> typedef tree (*valueizer_t)(tree var);
>
> class gimple_combine
> {
> public:
>   gimple_combine(nonzerobits_t a, valueizer_t b) : nonzerobitsf(a),
> valueizerv(b), allow_full_reassiocation(false) {}
>   gimple_combine() : nonzerobitsf(NULL), valueizerv(NULL),
> allow_full_reassiocation(false) {}
>   gimple_combine(bool reas) : nonzerobitsf(NULL), valueizerv(NULL),
> allow_full_reassiocation(reas) {}
>   tree build2 (location_t, enum tree_code, tree, tree, tree);
>   tree build1 (location_t, enum tree_code, tree, tree);
>   tree build3 (location_t, enum tree_code, tree, tree, tree, tree);
>   tree combine (gimple);
> private:
>   nonzerobits_t nonzerobitsf;
>   valueizer_t valueizerv;
>   bool allow_full_reassiocation;
>   tree binary (location_t, enum tree_code, tree, tree, tree);
>   tree unary (location_t, enum tree_code, tree, tree);
>   tree ternary (location_t, enum tree_code, tree, tree, tree, tree);
> };
>
> bool replace_rhs_after_ssa_combine (gimple_stmt_iterator *, tree);
>
> This is what I have so far and wonder if there is anything else I
> should include.
>
> This will be used to replace the folding code in fold-const.c and gimple-fold.c.

I placed what I decided in a branch in git:

http://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/gimple-ssa-combine.h;h=3d597291c1756cdf6e3318fd190ac70911ceb702;hb=d32468a31ab5e50fabab3a04303f6892ad890fd5

Note I won't have time to work on this again until the middle of August or so.

The status of the current patch is that it is able to build libgcc but
there are some addition ICEs due to checking to make sure all of the
forwprop optimizations are pushed over to gimple_combine (since I
started this work on an older code base).

Thanks,
Andrew Pinski

>
> Thanks,
> Andrew Pinski

Re: RFC: Gimple combine/folding interface

[Richard Biener]

Andrew Pinski <pinskia@gmail.com> wrote:

>On Fri, Jul 19, 2013 at 5:09 PM, Andrew Pinski <pinskia@gmail.com>
>wrote:
>> I was creating a new gimple/folding interface and wanted some
>opinions
>> on the interface.
>>
>> typedef double_int (*nonzerobits_t)(tree var);
>> typedef tree (*valueizer_t)(tree var);
>>
>> class gimple_combine
>> {
>> public:
>>   gimple_combine(nonzerobits_t a, valueizer_t b) : nonzerobitsf(a),
>> valueizerv(b), allow_full_reassiocation(false) {}
>>   gimple_combine() : nonzerobitsf(NULL), valueizerv(NULL),
>> allow_full_reassiocation(false) {}
>>   gimple_combine(bool reas) : nonzerobitsf(NULL), valueizerv(NULL),
>> allow_full_reassiocation(reas) {}
>>   tree build2 (location_t, enum tree_code, tree, tree, tree);
>>   tree build1 (location_t, enum tree_code, tree, tree);
>>   tree build3 (location_t, enum tree_code, tree, tree, tree, tree);
>>   tree combine (gimple);
>> private:
>>   nonzerobits_t nonzerobitsf;
>>   valueizer_t valueizerv;
>>   bool allow_full_reassiocation;
>>   tree binary (location_t, enum tree_code, tree, tree, tree);
>>   tree unary (location_t, enum tree_code, tree, tree);
>>   tree ternary (location_t, enum tree_code, tree, tree, tree, tree);
>> };

Just a few comments before I return to work late in August.  I like the way of using a c++ object to store combiner flags as opposed to extra arguments. For the optimizers I want to retain the ability to specify the desired result (constant, single op, arbitrary) which also allows shortcutting some transforms.
I also want to retain the ability to return the combining result piecewise without building trees, at least for results that fit a single gimple stmt.

>> bool replace_rhs_after_ssa_combine (gimple_stmt_iterator *, tree);

... Precisely to avoid this.

I'm not sure if you want to replace the fold-const.c workers with this infrastructure?

Richard.

>> This is what I have so far and wonder if there is anything else I
>> should include.
>>
>> This will be used to replace the folding code in fold-const.c and
>gimple-fold.c.
>
>I placed what I decided in a branch in git:
>
>http://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/gimple-ssa-combine.h;h=3d597291c1756cdf6e3318fd190ac70911ceb702;hb=d32468a31ab5e50fabab3a04303f6892ad890fd5
>
>Note I won't have time to work on this again until the middle of August
>or so.
>
>The status of the current patch is that it is able to build libgcc but
>there are some addition ICEs due to checking to make sure all of the
>forwprop optimizations are pushed over to gimple_combine (since I
>started this work on an older code base).
>
>Thanks,
>Andrew Pinski
>
>>
>> Thanks,
>> Andrew Pinski

Re: RFC: Gimple combine/folding interface

[Florian Weimer]

On 07/20/2013 02:09 AM, Andrew Pinski wrote:
>    gimple_combine(bool reas) : nonzerobitsf(NULL), valueizerv(NULL),
> allow_full_reassiocation(reas) {}

I think this constructor should be marked "explicit".

-- 
Florian Weimer / Red Hat Product Security Team

Re: RFC: Gimple combine/folding interface

[Jeff Law]

On 07/21/2013 08:14 PM, Andrew Pinski wrote:
> On Fri, Jul 19, 2013 at 5:09 PM, Andrew Pinski <pinskia@gmail.com> wrote:
>> I was creating a new gimple/folding interface and wanted some opinions
>> on the interface.
>>
>> typedef double_int (*nonzerobits_t)(tree var);
>> typedef tree (*valueizer_t)(tree var);
>>
>> class gimple_combine
>> {
>> public:
>>    gimple_combine(nonzerobits_t a, valueizer_t b) : nonzerobitsf(a),
IIRC, the zero/nonzero bits stuff in combine is mostly good at pruning 
sign/zero extensions, eliminating bit masking in the low bits for alphas 
and for cleaning up addressing of varargs arguments that were on the 
stack.  Yea, there are times when it can do other stuff, but that's my 
recollection for what it was actually good at.

Before designing an interface which inherently includes that information 
we should think hard about if it's valuable and if a tree combiner is 
the right place.

I have high hopes that we can get the zero/sign extension elimination we 
want by carrying VRP information and querying it.

As Richi has mentioned, we really want a folder we can call 
independently of whatever pass we're in.  Though I'd also like a folder 
that can query for pass specific information if it's handy and useful.

One of the interesting things we're going to need to figure out is when 
walking the use-def chains do we want to build the more complex 
expression, then fold it, keeping the result if it's gimple.  Or do we 
want to work strictly with an exploded operator/operands represenation.

Jeff

Re: RFC: Gimple combine/folding interface

[Jakub Jelinek]

On Mon, Jul 22, 2013 at 01:36:17PM -0600, Jeff Law wrote:
> Before designing an interface which inherently includes that
> information we should think hard about if it's valuable and if a
> tree combiner is the right place.
> 
> I have high hopes that we can get the zero/sign extension
> elimination we want by carrying VRP information and querying it.
> 
> As Richi has mentioned, we really want a folder we can call
> independently of whatever pass we're in.  Though I'd also like a
> folder that can query for pass specific information if it's handy
> and useful.

For the preservation of VRP info we already have patch in process of review:
http://gcc.gnu.org/ml/gcc-patches/2013-07/msg00121.html

As for zero bits info, I've recently run into a case where having the zero
bits information preserved alongside of the VRP info could be helpful,
for optimizing away the vectorizer scalar loop for bound.  If non-zero bits
computation proves or e.g. user asserts through if (val % 32)
__builtin_unreachable () or similar, even when the bounds of the loop aren't
constant, we could figure out that the number of iterations is a multiply of
vectorization factor and avoid computing that

So, perhaps let vrp{1,2} compute the vrp info and preserve (plus if not
specified just set nonzero bits to all ones), and this pass or other compute
the nonzero bits?  Sign bit copies is just an int, perhaps also track that.

	Jakub