RFC: Add of type-demotion pass

Hello,

These passes are implementing type-demotion (type sinking into statements) for some gimple statements.  I limitted inital implementation to the set of multiply, addition, substraction, and binary-and/or/xor.  Additional this pass adds some rules to sink type-cast sequences - eg. (int) (short) x; with char as type of x.  This special handing in this pass of such type-sequence simplification is necessary to avoid too complex cast-sequences by type-unsigned conversion used by this pass to avoid undefined overflow behaviour.

I will sent separate patch with some test-cases to demonstrate and verify operation of this new optimization.  Just one sample I will cite here to demonstrate operation of type-demotion pass.

------start-----
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */

signed char a[1024], b[1024];

void
baz (void)
{
  int i, s, t;
  for (i = 0; i < 1024; i++)
    { s = a[i]; t = b[i]; s += t + 0x12345600; a[i] = s; }
}

/* { dg-final { scan-tree-dump-times "305419776" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
------end------

You will notice that by typedemote2 pass the 's += t + 0x12345600;' expression gets simplified to 's += t + 0;'.

I have added an additional early pass "typedemote1" to this patch for simple cases types can be easily sunken into statement without special unsigned-cast for overflow-case.   Jakub asked for it. Tests have shown that this pass does optimizations in pretty few cases.  As example in testsuite see for example pr46867.c testcase.
The second pass (I put it behind first vrp pass to avoid testcase-conflicts) uses 'unsigned'-type casts to avoid undefined overflow behavior. This pass has much more hits in standard code, but seems to trigger some regressions in vect pass:

List of regi

FAIL: gcc.dg/vect/slp-cond-3.c scan-tree-dump-times vect "vectorizing stmts using SLP" 1
FAIL: gcc.dg/vect/vect-reduc-dot-s8b.c -flto  scan-tree-dump-times vect "vect_recog_widen_mult_pattern: detected" 1
FAIL: gcc.dg/vect/slp-cond-3.c -flto  scan-tree-dump-times vect "vectorizing stmts using SLP" 1
FAIL: gcc.target/i386/rotate-1.c scan-assembler ro[lr]b


2013-07-08  Kai Tietz  <ktietz@redhat.com>

	* Makefile.in (OBJS): Add tree-ssa-te.o
	* passes.c (init_optimization_passes): Add
	pass_type_demote1 and pass_type_demote2.
	tree-pass.h (pass_type_demote1): Add declaration.
	(pass_type_demote2): Likewise.
	* tree-ssa-te.c: New implementation file.

Patch is tested for x86_64-unknown-linux-gnu, and x86_64-w64-mingw32. Ok for apply?

Regards,
Kai

On Mon, 8 Jul 2013, Kai Tietz wrote:

> These passes are implementing type-demotion (type sinking into 
> statements) for some gimple statements.  I limitted inital 
> implementation to the set of multiply, addition, substraction, and 
> binary-and/or/xor.  Additional this pass adds some rules to sink 
> type-cast sequences - eg. (int) (short) x; with char as type of x. 
> This special handing in this pass of such type-sequence simplification 
> is necessary to avoid too complex cast-sequences by type-unsigned 
> conversion used by this pass to avoid undefined overflow behaviour.

Hello,

thanks for working on this. This seems like a nice chance for me to learn, 
so I am trying to understand your patch, and I would be glad if you could 
give me a couple hints.

I wonder why you implemented this as a separate pass instead of adding it 
to tree-ssa-forwprop. demote_cast is (or should be) a special case of 
combine_conversions, so it would be nice to avoid the code duplication 
(there is also a version in fold-const.c). demote_into could be called 
from roughly the same place as simplify_conversion_from_bitmask. And you 
could reuse get_prop_source_stmt, can_propagate_from, 
remove_prop_source_from_use, etc.

If I understand, the main reason is because you want to go through the 
statements in reverse order, since this is the way the casts are being 
propagated (would forwprop also work, just more slowly, or would it miss 
opportunities across basic blocks?).

I have some trouble understanding why something as complicated as 
build_and_add_sum (which isn't restricted to additions by the way) is 
needed. Could you add a comment to the code explaining why you need to 
insert the statements precisely there and not for instance just before 
their use? Is that to try and help CSE?

> I have added an additional early pass "typedemote1" to this patch for simple cases types can be easily sunken into statement without special unsigned-cast for overflow-case.   Jakub asked for it. Tests have shown that this pass does optimizations in pretty few cases.  As example in testsuite see for example pr46867.c testcase.
> The second pass (I put it behind first vrp pass to avoid testcase-conflicts) uses 'unsigned'-type casts to avoid undefined overflow behavior. This pass has much more hits in standard code,

I assume that, when the pass is done, we can consider removing the 
corresponding code from the front-ends? That would increase the hits ;-)

----- Original Message -----
> On Mon, 8 Jul 2013, Kai Tietz wrote:
> 
> > These passes are implementing type-demotion (type sinking into
> > statements) for some gimple statements.  I limitted inital
> > implementation to the set of multiply, addition, substraction, and
> > binary-and/or/xor.  Additional this pass adds some rules to sink
> > type-cast sequences - eg. (int) (short) x; with char as type of x.
> > This special handing in this pass of such type-sequence simplification
> > is necessary to avoid too complex cast-sequences by type-unsigned
> > conversion used by this pass to avoid undefined overflow behaviour.
> 
> Hello,
> 
> thanks for working on this. This seems like a nice chance for me to learn,
> so I am trying to understand your patch, and I would be glad if you could
> give me a couple hints.

I try.
 
> I wonder why you implemented this as a separate pass instead of adding it
> to tree-ssa-forwprop. demote_cast is (or should be) a special case of
> combine_conversions, so it would be nice to avoid the code duplication
> (there is also a version in fold-const.c). demote_into could be called
> from roughly the same place as simplify_conversion_from_bitmask. And you
> could reuse get_prop_source_stmt, can_propagate_from,
> remove_prop_source_from_use, etc.

Initial patch (from last year) actual implemented that in forwprop.  I was then kindly asked to put this into a separate pass.  There are some good reason why forward-propagation isn't the right place for it.  Eg, forwprop does type-raising by default.  So by implementing type-demotion there too, would lead to raise-condition.  So there would be required additionally that within forwprop a straight line-depth conversion is done for statement-lists.  All this doesn't fit pretty well into current concept of forward-propagation ...
The cast demotion is of course something of interest for folding and might be fitting into forward-propagation-pass too.  The main cause why it is implemented within demotion pass is, that this pass introduces such cast-demotion-folding opportunities due its "unsigned"-type expansion.  So we want
to fold that within pass and not waiting until a later pass optimizes such redundant sequences away.

Btw, the cast-demotion can be still improved for some cases - see here as example the gcc.target/i386/rotate-1.c testcase for such an improvement - so that some expressions of the form of (type1) (((type2) x) op ((type2) y)) can be transformed into x op y.

> If I understand, the main reason is because you want to go through the
> statements in reverse order, since this is the way the casts are being
> propagated (would forwprop also work, just more slowly, or would it miss
> opportunities across basic blocks?).
It would miss some opportunities, and causes penalty on speed due concept of forwprop.
 
> I have some trouble understanding why something as complicated as
> build_and_add_sum (which isn't restricted to additions by the way) is
> needed. Could you add a comment to the code explaining why you need to
> insert the statements precisely there and not for instance just before
> their use? Is that to try and help CSE?
Yes, this function is a bit more complex as actual required for now in general.  Nevertheless required.  And I expect that demotion-pass will improve and so even the right now "unlikely" cases might be required more frequent.  I had in front lighter version of statement addition, but it failed in some cases.In some (rare) cases we would otherwise choose wrong basic-block to add the new "cast"-statements.  Well, there is another place (reassoc) where you can find nearly the same function, and its needs are exactly the same as within demote-pass.

> > I have added an additional early pass "typedemote1" to this patch for
> > simple cases types can be easily sunken into statement without special
> > unsigned-cast for overflow-case.   Jakub asked for it. Tests have shown
> > that this pass does optimizations in pretty few cases.  As example in
> > testsuite see for example pr46867.c testcase.
> > The second pass (I put it behind first vrp pass to avoid
> > testcase-conflicts) uses 'unsigned'-type casts to avoid undefined overflow
> > behavior. This pass has much more hits in standard code,
> 
> I assume that, when the pass is done, we can consider removing the
> corresponding code from the front-ends? That would increase the hits ;-)

Hmm, well possible, but unlikely.  FE and ME are two pretty different things.  Sadly stuff isn't as clearly separated as it should be.  But well, I know there is work going on to achieve that in this area.
 
> --
> Marc Glisse
> 

Kai

On 07/08/2013 02:52 PM, Marc Glisse wrote:
>
> I wonder why you implemented this as a separate pass instead of adding
> it to tree-ssa-forwprop. demote_cast is (or should be) a special case of
> combine_conversions, so it would be nice to avoid the code duplication
> (there is also a version in fold-const.c). demote_into could be called
> from roughly the same place as simplify_conversion_from_bitmask. And you
> could reuse get_prop_source_stmt, can_propagate_from,
> remove_prop_source_from_use, etc.
That's a real good question; I find myself looking a lot at the bits in 
forwprop and I'm getting worried it's on its way to being an 
unmaintainable mess.  Sadly, I'm making things worse rather than better 
with my recent changes.  I'm still hoping more structure will become 
evident as I continue to work through various improvements.

I find myself also pondering these bits in a code motion model; what 
hasn't become clear yet is the driving motivation to show why thinking 
about this as a code motion problem is interesting.

Conceptually we can hoist casts to their earliest possible point and 
sink them to their latest possible point.  What are the benefits of 
those transformations and is there anything inherently good about 
actually moving the typecasts as opposed to just realizing the casts are 
in the IL and optimizing appropriately.

ie, often I see the hoisting/sinking code bring a series of casts 
together into straighline code which then gets optimized.  *BUT* is 
there anything inherently better/easier with having them in straightline 
code.  We can walk the use->def chains and recover the same information. 
  If that's not happening, then that points to a failing in our optimizers.

Floating out there is the hope that there's a set of canonicalization 
rules to guide us where to place the typecasts.  ie, is it generally 
better to have

(T) (a) OP (T) b

Or is it better to have
(T) (a OP b)

[ Assuming they're semantically the same. ]

Is it dependent on T and how T relates to the underlying target?  Are 
the guidelines likely the same for logicals vs arithmetic, etc?




>
> If I understand, the main reason is because you want to go through the
> statements in reverse order, since this is the way the casts are being
> propagated (would forwprop also work, just more slowly, or would it miss
> opportunities across basic blocks?).
SSA_NAME_DEF_STMT can cross block boundaries.


>
> I have some trouble understanding why something as complicated as
> build_and_add_sum (which isn't restricted to additions by the way) is
> needed. Could you add a comment to the code explaining why you need to
> insert the statements precisely there and not for instance just before
> their use? Is that to try and help CSE?
Hmm, I thought I had suggested that routine get renamed during an 
internal, informal review of Kai's work.

>
>> I have added an additional early pass "typedemote1" to this patch for
>> simple cases types can be easily sunken into statement without special
>> unsigned-cast for overflow-case.   Jakub asked for it. Tests have
>> shown that this pass does optimizations in pretty few cases.  As
>> example in testsuite see for example pr46867.c testcase.
>> The second pass (I put it behind first vrp pass to avoid
>> testcase-conflicts) uses 'unsigned'-type casts to avoid undefined
>> overflow behavior. This pass has much more hits in standard code,
>
> I assume that, when the pass is done, we can consider removing the
> corresponding code from the front-ends? That would increase the hits ;-)
Kai and I have briefly touched on this, mostly in the context of 
removing bits from fold-const.c rather than the front-ends proper.


jeff
>

On Tue, 9 Jul 2013, Kai Tietz wrote:

>> I would be glad if you could give me a couple hints.
> I try.

Thanks :-)

>> I wonder why you implemented this as a separate pass instead of adding it
>> to tree-ssa-forwprop. demote_cast is (or should be) a special case of
>> combine_conversions, so it would be nice to avoid the code duplication
>> (there is also a version in fold-const.c). demote_into could be called
>> from roughly the same place as simplify_conversion_from_bitmask. And you
>> could reuse get_prop_source_stmt, can_propagate_from,
>> remove_prop_source_from_use, etc.
>
> Initial patch (from last year) actual implemented that in forwprop.

Ah, reading the conversation from last year helped me understand a bit 
better.

> I was then kindly asked to put this into a separate pass.  There are 
> some good reason why forward-propagation isn't the right place for it. 
> Eg, forwprop does type-raising by default.

Even in cases where that increases the size of the operation? I see a 
hoist_conversion_for_bitop_p that seems to try and prevent it.

> So by implementing type-demotion 
> there too, would lead to raise-condition.  So there would be required 
> additionally that within forwprop a straight line-depth conversion is 
> done for statement-lists.  All this doesn't fit pretty well into current 
> concept of forward-propagation ... The cast demotion is of course 
> something of interest for folding and might be fitting into 
> forward-propagation-pass too.  The main cause why it is implemented 
> within demotion pass is, that this pass introduces such 
> cast-demotion-folding opportunities due its "unsigned"-type expansion. 
> So we want to fold that within pass and not waiting until a later pass 
> optimizes such redundant sequences away.

I hope we can at least find a way to share code between the passes.

>> If I understand, the main reason is because you want to go through the
>> statements in reverse order, since this is the way the casts are being
>> propagated (would forwprop also work, just more slowly, or would it miss
>> opportunities across basic blocks?).
> It would miss some opportunities,

Could you explain in what case? I guess my trouble understanding this is 
the same as in the next question, and I am missing a fundamental point...

> and causes penalty on speed due concept of forwprop.
>
>> I have some trouble understanding why something as complicated as
>> build_and_add_sum (which isn't restricted to additions by the way) is
>> needed. Could you add a comment to the code explaining why you need to
>> insert the statements precisely there and not for instance just before
>> their use? Is that to try and help CSE?
> Yes, this function is a bit more complex as actual required for now in 
> general.  Nevertheless required.  And I expect that demotion-pass will 
> improve and so even the right now "unlikely" cases might be required 
> more frequent.  I had in front lighter version of statement addition, 
> but it failed in some cases.In some (rare) cases we would otherwise 
> choose wrong basic-block to add the new "cast"-statements.  Well, there 
> is another place (reassoc) where you can find nearly the same function, 
> and its needs are exactly the same as within demote-pass.

I had a look at the reassoc pass and failed to understand the logic there 
as well :-( I don't really understand how the basic block can be wrong. If 
we only handle the single use case with no side effects and no weird jump 
in between, nothing but the user should notice if you move the definition 
next to the use. So is this a way to handle weirder jumps than you could 
otherwise?

>>> I have added an additional early pass "typedemote1" to this patch for
>>> simple cases types can be easily sunken into statement without special
>>> unsigned-cast for overflow-case.   Jakub asked for it. Tests have shown
>>> that this pass does optimizations in pretty few cases.  As example in
>>> testsuite see for example pr46867.c testcase.
>>> The second pass (I put it behind first vrp pass to avoid
>>> testcase-conflicts) uses 'unsigned'-type casts to avoid undefined overflow
>>> behavior. This pass has much more hits in standard code,

My little understanding from the old conversation and Jeff's post in this 
thread is that there are 2 ways to think about this optimization:

1) the canonical representation is with the smallest type possible. Using 
forwprop could make sense there (even if it may need help from another 
pass for some complicated cases, and it isn't the most efficient way). 
There is possibly a late pass to change all the types too small for the 
hardware into int.

2) we compute for each operation what minimal size it needs. Then, we may 
do some optimizations (truncate constants), possibly convert the 
operations to some smaller type (many at once), but not necessarily. This 
requires a separate pass but doesn't look like what you are doing.



On Tue, 9 Jul 2013, Jeff Law wrote:

> On 07/08/2013 02:52 PM, Marc Glisse wrote:
>> 
>> I wonder why you implemented this as a separate pass instead of adding
>> it to tree-ssa-forwprop. demote_cast is (or should be) a special case of
>> combine_conversions, so it would be nice to avoid the code duplication
>> (there is also a version in fold-const.c). demote_into could be called
>> from roughly the same place as simplify_conversion_from_bitmask. And you
>> could reuse get_prop_source_stmt, can_propagate_from,
>> remove_prop_source_from_use, etc.
> That's a real good question; I find myself looking a lot at the bits in 
> forwprop and I'm getting worried it's on its way to being an unmaintainable 
> mess.  Sadly, I'm making things worse rather than better with my recent 
> changes.  I'm still hoping more structure will become evident as I continue 
> to work through various improvements.

It looks to me like a gimple version of fold, except that since it is 
gimple, basic operations are an order of magnitude more complicated. But I 
don't really see why that would make it an unmaintainable mess, giant 
switches are not that bad.

>> If I understand, the main reason is because you want to go through the
>> statements in reverse order, since this is the way the casts are being
>> propagated (would forwprop also work, just more slowly, or would it miss
>> opportunities across basic blocks?).
> SSA_NAME_DEF_STMT can cross block boundaries.

I know, which is why it isn't obvious to me what opportunities are missed.

>> I assume that, when the pass is done, we can consider removing the
>> corresponding code from the front-ends? That would increase the hits ;-)
> Kai and I have briefly touched on this, mostly in the context of removing 
> bits from fold-const.c rather than the front-ends proper.

The code in the front-ends is a pain. Lately, it made implementing some 
parts of the undefined behavior sanitizer much more complicated than it 
should have been. I think fold-const hurts less than optimization code 
directly in the front-ends.

Thanks Kai and Jeff, your posts helped a lot,

On 07/12/2013 01:13 PM, Marc Glisse wrote:
>> Initial patch (from last year) actual implemented that in forwprop.
>
> Ah, reading the conversation from last year helped me understand a bit
> better.
It's also worth noting that fold-const.c also does some type 
hoisting/sinking.   Ideally that code should just be going away.


>> So by implementing type-demotion there too, would lead to
>> raise-condition.  So there would be required additionally that within
>> forwprop a straight line-depth conversion is done for
>> statement-lists.  All this doesn't fit pretty well into current
>> concept of forward-propagation ... The cast demotion is of course
>> something of interest for folding and might be fitting into
>> forward-propagation-pass too.  The main cause why it is implemented
>> within demotion pass is, that this pass introduces such
>> cast-demotion-folding opportunities due its "unsigned"-type expansion.
>> So we want to fold that within pass and not waiting until a later pass
>> optimizes such redundant sequences away.
>
> I hope we can at least find a way to share code between the passes.
Well, I'd like to pull all of the type hoisting/sinking code out to its 
own pass.  That may be a bit idealistic, but that's my hope/goal.


>
>>> If I understand, the main reason is because you want to go through the
>>> statements in reverse order, since this is the way the casts are being
>>> propagated (would forwprop also work, just more slowly, or would it miss
>>> opportunities across basic blocks?).
>> It would miss some opportunities,
>
> Could you explain in what case? I guess my trouble understanding this is
> the same as in the next question, and I am missing a fundamental point...
Anytime you hoist/sink a cast, you're moving it across an operation -- 
which can expose it as a redundant cast.

Let's say you start with

A = (T) x1;
B = (T) x2;
R = A & B;


And sink the cast after the operation like this:

C = x1 & x2;
R = (T) C;

We may find that that cast of C to type T is redundant.  Similar cases 
can be found when we hoist the cast across the operation.  I saw this 
kind of situation occur regularly when I was looking at Kai's 
hoisting/sinking patches.

Now I believe one of Kai's goals is to allow our various pattern based 
folders to work better by not having to account for casting operations 
as often in sequences of statements we want to fold.  I suspect that to 
see benefit from that we'd have to hoist, fold, sink, fold.  That argues 
that hoisting/sinking should be independent of the folding step (which 
shouldn't be a surprise to any of us).


>> That's a real good question; I find myself looking a lot at the bits
>> in forwprop and I'm getting worried it's on its way to being an
>> unmaintainable mess.  Sadly, I'm making things worse rather than
>> better with my recent changes.  I'm still hoping more structure will
>> become evident as I continue to work through various improvements.
>
> It looks to me like a gimple version of fold, except that since it is
> gimple, basic operations are an order of magnitude more complicated. But
> I don't really see why that would make it an unmaintainable mess, giant
> switches are not that bad.
It's certainly moving towards a gimple version of fold and special 
casing everything as we convert from fold and to gimple_fold (or 
whatever we call it) is going to result in a horrid mess.

I find myself thinking that at a high level we need to split out the 
forward and backward propagation bits into distinct passes.  The 
backward propagation bits are just a tree combiner and the idioms used 
to follow the backward chains to create more complex trees and fold them 
need to be reusable components.  It's totally silly (and ultimately 
unmaintainable) that each transformation is open-coding the walking of 
the use-def chain and simplification step.

Jeff

Jeff Law <law@redhat.com> wrote:

>On 07/12/2013 01:13 PM, Marc Glisse wrote:
>>> Initial patch (from last year) actual implemented that in forwprop.
>>
>> Ah, reading the conversation from last year helped me understand a
>bit
>> better.
>It's also worth noting that fold-const.c also does some type 
>hoisting/sinking.   Ideally that code should just be going away.
>
>
>>> So by implementing type-demotion there too, would lead to
>>> raise-condition.  So there would be required additionally that
>within
>>> forwprop a straight line-depth conversion is done for
>>> statement-lists.  All this doesn't fit pretty well into current
>>> concept of forward-propagation ... The cast demotion is of course
>>> something of interest for folding and might be fitting into
>>> forward-propagation-pass too.  The main cause why it is implemented
>>> within demotion pass is, that this pass introduces such
>>> cast-demotion-folding opportunities due its "unsigned"-type
>expansion.
>>> So we want to fold that within pass and not waiting until a later
>pass
>>> optimizes such redundant sequences away.
>>
>> I hope we can at least find a way to share code between the passes.
>Well, I'd like to pull all of the type hoisting/sinking code out to its
>
>own pass.  That may be a bit idealistic, but that's my hope/goal.
>
>
>>
>>>> If I understand, the main reason is because you want to go through
>the
>>>> statements in reverse order, since this is the way the casts are
>being
>>>> propagated (would forwprop also work, just more slowly, or would it
>miss
>>>> opportunities across basic blocks?).
>>> It would miss some opportunities,
>>
>> Could you explain in what case? I guess my trouble understanding this
>is
>> the same as in the next question, and I am missing a fundamental
>point...
>Anytime you hoist/sink a cast, you're moving it across an operation -- 
>which can expose it as a redundant cast.
>
>Let's say you start with
>
>A = (T) x1;
>B = (T) x2;
>R = A & B;
>
>
>And sink the cast after the operation like this:
>
>C = x1 & x2;
>R = (T) C;
>
>We may find that that cast of C to type T is redundant.  Similar cases 
>can be found when we hoist the cast across the operation.  I saw this 
>kind of situation occur regularly when I was looking at Kai's 
>hoisting/sinking patches.
>
>Now I believe one of Kai's goals is to allow our various pattern based 
>folders to work better by not having to account for casting operations 
>as often in sequences of statements we want to fold.  I suspect that to
>
>see benefit from that we'd have to hoist, fold, sink, fold.  That
>argues 
>that hoisting/sinking should be independent of the folding step (which 
>shouldn't be a surprise to any of us).
>
>
>>> That's a real good question; I find myself looking a lot at the bits
>>> in forwprop and I'm getting worried it's on its way to being an
>>> unmaintainable mess.  Sadly, I'm making things worse rather than
>>> better with my recent changes.  I'm still hoping more structure will
>>> become evident as I continue to work through various improvements.
>>
>> It looks to me like a gimple version of fold, except that since it is
>> gimple, basic operations are an order of magnitude more complicated.
>But
>> I don't really see why that would make it an unmaintainable mess,
>giant
>> switches are not that bad.
>It's certainly moving towards a gimple version of fold and special 
>casing everything as we convert from fold and to gimple_fold (or 
>whatever we call it) is going to result in a horrid mess.
>
>I find myself thinking that at a high level we need to split out the 
>forward and backward propagation bits into distinct passes.  The 
>backward propagation bits are just a tree combiner and the idioms used 
>to follow the backward chains to create more complex trees and fold
>them 
>need to be reusable components.  It's totally silly (and ultimately 
>unmaintainable) that each transformation is open-coding the walking of 
>the use-def chain and simplification step.

Splitting forward and backward propagation into separate passes creates a pass ordering issue. Rather than that all forward propagations should be formulated as backward or the other way around. A bit awkward in some cases maybe, but you can at least drive forward propagations from their sinks.

As of a type demotion pass - I'd rather have this kind of thing as a lowering exposing mode promotion somewhen late in the simple optimizing stage.

Btw, other demotions still happen from convert.c ...

Richard.

>Jeff

On Fri, 19 Jul 2013, Jeff Law wrote:

> It's also worth noting that fold-const.c also does some type 
> hoisting/sinking.

fold-const.c does everything ;-)

> Ideally that code should just be going away.

Like most of the code from fold-const.c that isn't about folding 
constants, I guess, once it has a replacement at the gimple level.

>>>> If I understand, the main reason is because you want to go through the
>>>> statements in reverse order, since this is the way the casts are being
>>>> propagated (would forwprop also work, just more slowly, or would it miss
>>>> opportunities across basic blocks?).
>>> It would miss some opportunities,
>> 
>> Could you explain in what case? I guess my trouble understanding this is
>> the same as in the next question, and I am missing a fundamental point...
> Anytime you hoist/sink a cast, you're moving it across an operation -- which 
> can expose it as a redundant cast.
>
> Let's say you start with
>
> A = (T) x1;
> B = (T) x2;
> R = A & B;
>
>
> And sink the cast after the operation like this:
>
> C = x1 & x2;
> R = (T) C;
>
> We may find that that cast of C to type T is redundant.  Similar cases can be 
> found when we hoist the cast across the operation.  I saw this kind of 
> situation occur regularly when I was looking at Kai's hoisting/sinking 
> patches.

IIRC the question here was how forwprop could miss opportunities that a 
backward (reverse dominance) walk finds, and I don't see that in this 
example. If the cast is redundant, forwprop is just as likely to detect 
it.

> Now I believe one of Kai's goals is to allow our various pattern based 
> folders to work better by not having to account for casting operations as 
> often in sequences of statements we want to fold.

Ah. I thought it was mostly so operations would be performed in a smaller, 
hopefully cheaper mode. Simplifying combiner patterns would be nice if 
that worked.

>>> That's a real good question; I find myself looking a lot at the bits
>>> in forwprop and I'm getting worried it's on its way to being an
>>> unmaintainable mess.  Sadly, I'm making things worse rather than
>>> better with my recent changes.  I'm still hoping more structure will
>>> become evident as I continue to work through various improvements.
>> 
>> It looks to me like a gimple version of fold, except that since it is
>> gimple, basic operations are an order of magnitude more complicated. But
>> I don't really see why that would make it an unmaintainable mess, giant
>> switches are not that bad.
> It's certainly moving towards a gimple version of fold and special casing 
> everything as we convert from fold and to gimple_fold (or whatever we call 
> it) is going to result in a horrid mess.
>
> I find myself thinking that at a high level we need to split out the forward 
> and backward propagation bits into distinct passes.

They are already mostly split (2 separate loops in 
ssa_forward_propagate_and_combine), so that wouldn't be hard.

> The backward propagation 
> bits are just a tree combiner and the idioms used to follow the backward 
> chains to create more complex trees and fold them need to be reusable 
> components.  It's totally silly (and ultimately unmaintainable) that each 
> transformation is open-coding the walking of the use-def chain and 
> simplification step.

It isn't completely open-coded. get_prop_source_stmt, can_propagate_from, 
defcodefor_name, etc make walking the use-def chain not so bad.

Usually at this point Richard refers to Andrew's work on a gimple 
combiner...

Marc Glisse <marc.glisse@inria.fr> wrote:

>On Fri, 19 Jul 2013, Jeff Law wrote:
>
>> It's also worth noting that fold-const.c also does some type 
>> hoisting/sinking.
>
>fold-const.c does everything ;-)
>
>> Ideally that code should just be going away.
>
>Like most of the code from fold-const.c that isn't about folding 
>constants, I guess, once it has a replacement at the gimple level.
>
>>>>> If I understand, the main reason is because you want to go through
>the
>>>>> statements in reverse order, since this is the way the casts are
>being
>>>>> propagated (would forwprop also work, just more slowly, or would
>it miss
>>>>> opportunities across basic blocks?).
>>>> It would miss some opportunities,
>>> 
>>> Could you explain in what case? I guess my trouble understanding
>this is
>>> the same as in the next question, and I am missing a fundamental
>point...
>> Anytime you hoist/sink a cast, you're moving it across an operation
>-- which 
>> can expose it as a redundant cast.
>>
>> Let's say you start with
>>
>> A = (T) x1;
>> B = (T) x2;
>> R = A & B;
>>
>>
>> And sink the cast after the operation like this:
>>
>> C = x1 & x2;
>> R = (T) C;
>>
>> We may find that that cast of C to type T is redundant.  Similar
>cases can be 
>> found when we hoist the cast across the operation.  I saw this kind
>of 
>> situation occur regularly when I was looking at Kai's
>hoisting/sinking 
>> patches.
>
>IIRC the question here was how forwprop could miss opportunities that a
>
>backward (reverse dominance) walk finds, and I don't see that in this 
>example. If the cast is redundant, forwprop is just as likely to detect
>
>it.
>
>> Now I believe one of Kai's goals is to allow our various pattern
>based 
>> folders to work better by not having to account for casting
>operations as 
>> often in sequences of statements we want to fold.
>
>Ah. I thought it was mostly so operations would be performed in a
>smaller, 
>hopefully cheaper mode. Simplifying combiner patterns would be nice if 
>that worked.
>
>>>> That's a real good question; I find myself looking a lot at the
>bits
>>>> in forwprop and I'm getting worried it's on its way to being an
>>>> unmaintainable mess.  Sadly, I'm making things worse rather than
>>>> better with my recent changes.  I'm still hoping more structure
>will
>>>> become evident as I continue to work through various improvements.
>>> 
>>> It looks to me like a gimple version of fold, except that since it
>is
>>> gimple, basic operations are an order of magnitude more complicated.
>But
>>> I don't really see why that would make it an unmaintainable mess,
>giant
>>> switches are not that bad.
>> It's certainly moving towards a gimple version of fold and special
>casing 
>> everything as we convert from fold and to gimple_fold (or whatever we
>call 
>> it) is going to result in a horrid mess.
>>
>> I find myself thinking that at a high level we need to split out the
>forward 
>> and backward propagation bits into distinct passes.
>
>They are already mostly split (2 separate loops in 
>ssa_forward_propagate_and_combine), so that wouldn't be hard.
>
>> The backward propagation 
>> bits are just a tree combiner and the idioms used to follow the
>backward 
>> chains to create more complex trees and fold them need to be reusable
>
>> components.  It's totally silly (and ultimately unmaintainable) that
>each 
>> transformation is open-coding the walking of the use-def chain and 
>> simplification step.

Yeah - ideally the pattern matching would be abstract enough that it works on trees, gimple and rtl ... Using a domain specific language like Haskell would get you pattern combining for free. But I suppose with c++ you can come close enough to at least support tree and gimple ssa.

>It isn't completely open-coded. get_prop_source_stmt,
>can_propagate_from, 
>defcodefor_name, etc make walking the use-def chain not so bad.
>
>Usually at this point Richard refers to Andrew's work on a gimple 
>combiner...

That or the gimple folding interface. Note the idea behind both should be to make the combined accessible from random passes just like we use fold_build now.

Richard.