[RFC] Improve Tree-SSA if-conversion - convergence of efforts

[RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Tehila Meyzels]

Hi,

I'd like to bring up on the list a discussion that a bunch of people (most
of those CC-ed above) started at the GCC Summit:

Lately, there were few efforts, that are not necessarily related to each
other, but are all relevant to if-conversion.
Each of them has its own restriction, like a specific control-flow, target
dependent information, permission to transform speculative loads, etc.

Few patches that I'm aware of are:
1.  Conditional store sinking, by Michael Matz:
http://gcc.gnu.org/ml/gcc-patches/2007-04/msg00724.html

2. If -conversion for multiple IF_THEN_ELSE clauses, by Victor Kaplansky:
http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html
Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
(2.3.3)

3.  (unconditional) Store sinking (4.1.1 based), by Revital Eres and Victor
Kaplansky:
http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html (same patch as
previous)
Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
(2.3.2)

4. Conditional load hoisting (4.1.1 based), by myself:
http://gcc.gnu.org/ml/gcc-patches/2007-07/msg02168.html

5. Maybe more?

You're welcome to share your/others related works here...


I'd like to suggest to converge all these efforts into a single improved
tree-level if-conversion pass (i.e., on the top of tree-if-conv.c).
Currently, the tree-level if-conversion pass is quite limited in several
ways, and mostly with respect to handling of loads/stores (it basically
doesn't handle them), but not only.

There are several reasons why to store-sinking and load-hoisting should be
combined with the if-conversion pass:
1. Store-sinking/load hoisting effect one another and they both can create
new opportunities for if-conversion (not only in vectorizable loops, for
example).
    Currently, load-store motion pass happens too late and thus don't help
the (tree-ssa) if-converter.
2. Store-sinking/load hoisting may have an overhead and may degrade
performance unless the relevant conditional branch gets if-converted.

Issues/Questions to be considered and discussed:
1. Cost model and machine dependency issues:
    - When is it profitable to perform these motions? What is the algorithm
to decide whether there is a good chance for if-conversion?
    - Target dependency - What to check?
      A. Are there scalar select/cmove/predicated instructions  (like in
SPU)?
      B. Are there vector select/cmove/predicated instructions (like in
PowerPC)? + will  the loop be vectorized?
      C. Are speculative loads allowed? Do memory accesses trap?
      D. More?

2. Which transformations we want to take care of in this pass?
   A. Conditional/unconditional loads/stores.
   B. PHI nodes with operands that are neither constants nor SSA NAMES
(Currently, this is not supported in tree-if-conv.c).
   C. PHIOPT transformations (i.e., merge the PHIOPT pass into this pass
maybe)?
   D More?
3. New control-flow graphs we want to support (besides the regular
IF_THEN_ELSE, diamond-based):
    A. Nested diamonds.
    B. Sequential diamonds.
    C. More?
4. After we complete this pass, will the RTL-level ifcvt be needed?
    I guess the answer is yes, but I would like to hear more opinions.

Any comments/ideas/thoughts are really appreciated.

Thanks,
Tehila.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Daniel Berlin]

On 7/31/07, Tehila Meyzels <TEHILA@il.ibm.com> wrote:
>
> Hi,
>
> I'd like to bring up on the list a discussion that a bunch of people (most
> of those CC-ed above) started at the GCC Summit:
>
> Lately, there were few efforts, that are not necessarily related to each
> other, but are all relevant to if-conversion.
> Each of them has its own restriction, like a specific control-flow, target
> dependent information, permission to transform speculative loads, etc.
>
> Few patches that I'm aware of are:
> 1.  Conditional store sinking, by Michael Matz:
> http://gcc.gnu.org/ml/gcc-patches/2007-04/msg00724.html
>
> 2. If -conversion for multiple IF_THEN_ELSE clauses, by Victor Kaplansky:
> http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html
> Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
> (2.3.3)
>
> 3.  (unconditional) Store sinking (4.1.1 based), by Revital Eres and Victor
> Kaplansky:
> http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html (same patch as
> previous)
> Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
> (2.3.2)
>
> 4. Conditional load hoisting (4.1.1 based), by myself:
> http://gcc.gnu.org/ml/gcc-patches/2007-07/msg02168.html
>
> 5. Maybe more?
>
> You're welcome to share your/others related works here...
>
>
> I'd like to suggest to converge all these efforts into a single improved
> tree-level if-conversion pass (i.e., on the top of tree-if-conv.c).
> Currently, the tree-level if-conversion pass is quite limited in several
> ways, and mostly with respect to handling of loads/stores (it basically
> doesn't handle them), but not only.
>
> There are several reasons why to store-sinking and load-hoisting should be
> combined with the if-conversion pass:
> 1. Store-sinking/load hoisting effect one another and they both can create
> new opportunities for if-conversion (not only in vectorizable loops, for
> example).

>     Currently, load-store motion pass happens too late and thus don't help
> the (tree-ssa) if-converter.
> 2. Store-sinking/load hoisting may have an overhead and may degrade
> performance unless the relevant conditional branch gets if-converted.

I agree with you for conditional stores/loads.

The unconditional store/load stuff, however, is exactly what
tree-ssa-sink was meant to do, and belongs there (this is #3 above).
I'm certainly going to fight tooth and nail against trying to shoehorn
unconditional store sinking into if-conv.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Michael Matz]

Hi,

On Tue, 31 Jul 2007, Daniel Berlin wrote:

> > 2. Store-sinking/load hoisting may have an overhead and may degrade
> > performance unless the relevant conditional branch gets if-converted.
> 
> I agree with you for conditional stores/loads.
> 
> The unconditional store/load stuff, however, is exactly what 
> tree-ssa-sink was meant to do, and belongs there (this is #3 above). I'm 
> certainly going to fight tooth and nail against trying to shoehorn 
> unconditional store sinking into if-conv.

FWIW I also agree that handling unconditional stores/loads does not belong 
in if-conv (or phi-opt), but in ssa-sink (or some similar transformation 
which can or can not use value numbers and the like).


Ciao,
Michael.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Tehila Meyzels]

Michael Matz <matz@suse.de> wrote on 31/07/2007 18:05:53:

> Hi,
>
> On Tue, 31 Jul 2007, Daniel Berlin wrote:
>
> > > 2. Store-sinking/load hoisting may have an overhead and may degrade
> > > performance unless the relevant conditional branch gets if-converted.
> >
> > I agree with you for conditional stores/loads.
> >
> > The unconditional store/load stuff, however, is exactly what
> > tree-ssa-sink was meant to do, and belongs there (this is #3 above).
I'm
> > certainly going to fight tooth and nail against trying to shoehorn
> > unconditional store sinking into if-conv.
>
> FWIW I also agree that handling unconditional stores/loads does not
belong
> in if-conv (or phi-opt), but in ssa-sink (or some similar transformation
> which can or can not use value numbers and the like).

OK.
And what's your opinion WRT conditional loads/stores?
Since you've sent your conditional store transformation patch,
I guess the meaning could be rewriting it on the top of tree-if-conv.

Tehila.

>
>
> Ciao,
> Michael.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Michael Matz]

Hi,

On Mon, 6 Aug 2007, Tehila Meyzels wrote:

> > in if-conv (or phi-opt), but in ssa-sink (or some similar transformation
> > which can or can not use value numbers and the like).
> 
> OK.
> 
> And what's your opinion WRT conditional loads/stores?
> Since you've sent your conditional store transformation patch,
> I guess the meaning could be rewriting it on the top of tree-if-conv.

Actually I'm not so sure about that.  I found the phi-opt infrastructure 
much better suited to do the necessary pattern matching, so I only 
thought of the conditional store replacement as enabling transformation.  
Also tree-if-conv only handles loops (and only inner ones), not general 
conditional patterns.  Something which might be fixable with some amount 
of work, but the phi-opt infrastructure simply was already there.


Ciao,
Michael.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Tehila Meyzels]

"Daniel Berlin" <dberlin@dberlin.org> wrote on 31/07/2007 18:00:57:

>
> I agree with you for conditional stores/loads.

Great!

>
> The unconditional store/load stuff, however, is exactly what
> tree-ssa-sink was meant to do, and belongs there (this is #3 above).
> I'm certainly going to fight tooth and nail against trying to shoehorn
> unconditional store sinking into if-conv.

Sometimes, store-sinking can cause performance degradations.
One reason for that, is increasing register pressure, due to extending life
range of registers.

In addition, in case we have a store followed by a branch, store sinking
result will be a branch followed by a store.
On some architectures, the former can be executed in parallel, as opposed
to the latter.
Thus, in this case, it worth executing store-sinking only when it helps the
if-conversion to get rid of the branch.

How do you suggest to solve this problem, in case store-sinking will be
part of the tree-sink pass?

Another point, what about (unconditional) load hoisting:
It's surely not related to sink pass, right?

Tehila.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Daniel Berlin]

On 8/1/07, Tehila Meyzels <TEHILA@il.ibm.com> wrote:
> "Daniel Berlin" <dberlin@dberlin.org> wrote on 31/07/2007 18:00:57:
>
> >
> > I agree with you for conditional stores/loads.
>
> Great!
>
> >
> > The unconditional store/load stuff, however, is exactly what
> > tree-ssa-sink was meant to do, and belongs there (this is #3 above).
> > I'm certainly going to fight tooth and nail against trying to shoehorn
> > unconditional store sinking into if-conv.
>
> Sometimes, store-sinking can cause performance degradations.
> One reason for that, is increasing register pressure, due to extending life
> range of registers.
>
> In addition, in case we have a store followed by a branch, store sinking
> result will be a branch followed by a store.
> On some architectures, the former can be executed in parallel, as opposed
> to the latter.
> Thus, in this case, it worth executing store-sinking only when it helps the
> if-conversion to get rid of the branch.
>

> How do you suggest to solve this problem, in case store-sinking will be
> part of the tree-sink pass?
>
Store sinking already *is* part of the tree-sink pass. It just only
sinks a small number of stores.
The solution to the problem that "sometimes you make things harder for
the target" is to fix that in the backend.  In this case, the
scheduler will take care of it.

All of our middle end optimizations will sometimes have bad effects
unless the backend fixes it up.    Trying to guess what is going to
happen 55 passes down the line is a bad idea unless you happen to be a
very good psychic.

As a general rule of thumb, we are happy to make the backend as target
specific and ask as many target questions as you like.  The middle
end, not so much.  There are very few passes in the middle end that
can/should/do ask anything about the target.  Store sinking is not one
of them, and I see no good reason it should be.

> Another point, what about (unconditional) load hoisting:
> It's surely not related to sink pass, right?
>
PRE already will hoist unconditional loads out of loops, and in places
where it will eliminate redundancy.

It could also hoist loads in non-redundancy situations, it is simply
the case that it's current heuristic  does not think this is a good
idea.

Thus, if you wanted to do unconditional load hoisting, the thing to do
is to make a function like do_regular_insertion in tree-ssa-pre.c, and
call it from insert_aux.

We already have another heuristic for partially antic fully available
expressions, see do_partial_partial_insertion

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Ayal Zaks]

"Daniel Berlin" <dberlin@dberlin.org> wrote on 01/08/2007 18:27:35:

> On 8/1/07, Tehila Meyzels <TEHILA@il.ibm.com> wrote:
> > "Daniel Berlin" <dberlin@dberlin.org> wrote on 31/07/2007 18:00:57:
> >
> > >
> > > I agree with you for conditional stores/loads.
> >
> > Great!
> >
> > >
> > > The unconditional store/load stuff, however, is exactly what
> > > tree-ssa-sink was meant to do, and belongs there (this is #3 above).
> > > I'm certainly going to fight tooth and nail against trying to
shoehorn
> > > unconditional store sinking into if-conv.
> >
> > Sometimes, store-sinking can cause performance degradations.
> > One reason for that, is increasing register pressure, due to extending
life
> > range of registers.
> >
> > In addition, in case we have a store followed by a branch, store
sinking
> > result will be a branch followed by a store.
> > On some architectures, the former can be executed in parallel, as
opposed
> > to the latter.
> > Thus, in this case, it worth executing store-sinking only when it helps
the
> > if-conversion to get rid of the branch.
> >
>
> > How do you suggest to solve this problem, in case store-sinking will be
> > part of the tree-sink pass?
> >
> Store sinking already *is* part of the tree-sink pass. It just only
> sinks a small number of stores.
> The solution to the problem that "sometimes you make things harder for
> the target" is to fix that in the backend.  In this case, the
> scheduler will take care of it.
>
> All of our middle end optimizations will sometimes have bad effects
> unless the backend fixes it up.    Trying to guess what is going to
> happen 55 passes down the line is a bad idea unless you happen to be a
> very good psychic.
>
> As a general rule of thumb, we are happy to make the backend as target
> specific and ask as many target questions as you like.  The middle
> end, not so much.  There are very few passes in the middle end that
> can/should/do ask anything about the target.  Store sinking is not one
> of them, and I see no good reason it should be.
>
> > Another point, what about (unconditional) load hoisting:
> > It's surely not related to sink pass, right?
> >
> PRE already will hoist unconditional loads out of loops, and in places
> where it will eliminate redundancy.
>
> It could also hoist loads in non-redundancy situations, it is simply
> the case that it's current heuristic  does not think this is a good
> idea.
>

Hoisting a non-redundant load speculatively above an if may indeed be a bad
idea, unless that if gets converted as a result (and possibly even then
...).  Are we in agreement then that unconditional load/store motion for
the sake of redundancy elimination continues to belong to PRE/tree-sink,
and that conditional load/store motion for the sake of conditional-branch
elimination better be coordinated by if-cvt?

Ayal.

> Thus, if you wanted to do unconditional load hoisting, the thing to do
> is to make a function like do_regular_insertion in tree-ssa-pre.c, and
> call it from insert_aux.
>
> We already have another heuristic for partially antic fully available
> expressions, see do_partial_partial_insertion

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Daniel Berlin]

On 8/1/07, Ayal Zaks <ZAKS@il.ibm.com> wrote:
> "Daniel Berlin" <dberlin@dberlin.org> wrote on 01/08/2007 18:27:35:
>
> > On 8/1/07, Tehila Meyzels <TEHILA@il.ibm.com> wrote:
> > > "Daniel Berlin" <dberlin@dberlin.org> wrote on 31/07/2007 18:00:57:
> > >
> > > >
> > > > I agree with you for conditional stores/loads.
> > >
> > > Great!
> > >
> > > >
> > > > The unconditional store/load stuff, however, is exactly what
> > > > tree-ssa-sink was meant to do, and belongs there (this is #3 above).
> > > > I'm certainly going to fight tooth and nail against trying to
> shoehorn
> > > > unconditional store sinking into if-conv.
> > >
> > > Sometimes, store-sinking can cause performance degradations.
> > > One reason for that, is increasing register pressure, due to extending
> life
> > > range of registers.
> > >
> > > In addition, in case we have a store followed by a branch, store
> sinking
> > > result will be a branch followed by a store.
> > > On some architectures, the former can be executed in parallel, as
> opposed
> > > to the latter.
> > > Thus, in this case, it worth executing store-sinking only when it helps
> the
> > > if-conversion to get rid of the branch.
> > >
> >
> > > How do you suggest to solve this problem, in case store-sinking will be
> > > part of the tree-sink pass?
> > >
> > Store sinking already *is* part of the tree-sink pass. It just only
> > sinks a small number of stores.
> > The solution to the problem that "sometimes you make things harder for
> > the target" is to fix that in the backend.  In this case, the
> > scheduler will take care of it.
> >
> > All of our middle end optimizations will sometimes have bad effects
> > unless the backend fixes it up.    Trying to guess what is going to
> > happen 55 passes down the line is a bad idea unless you happen to be a
> > very good psychic.
> >
> > As a general rule of thumb, we are happy to make the backend as target
> > specific and ask as many target questions as you like.  The middle
> > end, not so much.  There are very few passes in the middle end that
> > can/should/do ask anything about the target.  Store sinking is not one
> > of them, and I see no good reason it should be.
> >
> > > Another point, what about (unconditional) load hoisting:
> > > It's surely not related to sink pass, right?
> > >
> > PRE already will hoist unconditional loads out of loops, and in places
> > where it will eliminate redundancy.
> >
> > It could also hoist loads in non-redundancy situations, it is simply
> > the case that it's current heuristic  does not think this is a good
> > idea.
> >
>
> Hoisting a non-redundant load speculatively above an if may indeed be a bad
> idea, unless that if gets converted as a result (and possibly even then
> ...).  Are we in agreement then that unconditional load/store motion for
> the sake of redundancy elimination continues to belong to PRE/tree-sink,
> and that conditional load/store motion for the sake of conditional-branch
> elimination better be coordinated by if-cvt?
>

Yes.
My only issue here is duplication of code that exists in other passes,
not one of who/when/why things get done.

IE it is easier to use PRE's infrastructure to do the unconditional
load elimination, but still only do more than redundancy elimination
when you will if-convert branches, then it would be to write a new
pass.  Your new pass would end up probably missing loads that PRE goes
to trouble to get, and would duplicate a lot of the safety computation
PRE already knows how to do.

Of course, if you only see yourself moving 1 or two loads per
function, it may be quicker to do just those in their own pass
controlled by ifcvt.  But if you are going to try to if-convert every
branch, and every load inside those branches, you really don't want to
try to make your computation as efficient as PRE makes it.

A similar situation exists for unconditional store sinking/tree-ssa-sink.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[trevor_smigiel]

Tehila asked me a while ago to comment based on my experience with the
RTL if convert pass and the discussions some of us had at the GCC
summit.  Sorry it took me so long to respond.

The target I care about (Cell SPU) has some things that make an
aggressive if convert very useful and profitable.  It has conditional
moves for every mode (there is a single, unified register file), never
traps on illegal addresses (addresses always wrap to the 256KB address
space), and branches are expensive (there is no hardware cache).

The main limitation with the RTL if-convert pass is that it only
recognizes specific patterns.  It is easy to write a complicated if
statement (just using normal C with &&/||) that would never get
converted because it ends up with basic blocks that have many in edges
that if-convert generally doesn't handle.   (In our internal tree we
modified the RTL pass to handle some cases of multiple in-edges, and can
handle any number of insns in a basic block.)

I haven't looked at the tree-SSA if-convert code yet, but based on what
was described to me at the summit it seemed to be taking the same
approach as the RTL pass.  Recognize certain patterns and convert it.

I would like to see an approach that is able to take an arbitrary flow
graph without backedges and convert it to straight line code, limited
only by the cost model and impossible cases (e.g., inline asm).  

I'm not sure how that would be achieved in a target neutral way.

Trevor


* Tehila Meyzels <TEHILA@il.ibm.com> [2007-07-31 06:50]:
> 
> Hi,
> 
> I'd like to bring up on the list a discussion that a bunch of people (most
> of those CC-ed above) started at the GCC Summit:
> 
> Lately, there were few efforts, that are not necessarily related to each
> other, but are all relevant to if-conversion.
> Each of them has its own restriction, like a specific control-flow, target
> dependent information, permission to transform speculative loads, etc.
> 
> Few patches that I'm aware of are:
> 1.  Conditional store sinking, by Michael Matz:
> http://gcc.gnu.org/ml/gcc-patches/2007-04/msg00724.html
> 
> 2. If -conversion for multiple IF_THEN_ELSE clauses, by Victor Kaplansky:
> http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html
> Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
> (2.3.3)
> 
> 3.  (unconditional) Store sinking (4.1.1 based), by Revital Eres and Victor
> Kaplansky:
> http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00265.html (same patch as
> previous)
> Also mentioned here:  http://gcc.gnu.org/wiki/AutovectBranchOptimizations
> (2.3.2)
> 
> 4. Conditional load hoisting (4.1.1 based), by myself:
> http://gcc.gnu.org/ml/gcc-patches/2007-07/msg02168.html
> 
> 5. Maybe more?
> 
> You're welcome to share your/others related works here...
> 
> 
> I'd like to suggest to converge all these efforts into a single improved
> tree-level if-conversion pass (i.e., on the top of tree-if-conv.c).
> Currently, the tree-level if-conversion pass is quite limited in several
> ways, and mostly with respect to handling of loads/stores (it basically
> doesn't handle them), but not only.
> 
> There are several reasons why to store-sinking and load-hoisting should be
> combined with the if-conversion pass:
> 1. Store-sinking/load hoisting effect one another and they both can create
> new opportunities for if-conversion (not only in vectorizable loops, for
> example).
>     Currently, load-store motion pass happens too late and thus don't help
> the (tree-ssa) if-converter.
> 2. Store-sinking/load hoisting may have an overhead and may degrade
> performance unless the relevant conditional branch gets if-converted.
> 
> Issues/Questions to be considered and discussed:
> 1. Cost model and machine dependency issues:
>     - When is it profitable to perform these motions? What is the algorithm
> to decide whether there is a good chance for if-conversion?
>     - Target dependency - What to check?
>       A. Are there scalar select/cmove/predicated instructions  (like in
> SPU)?
>       B. Are there vector select/cmove/predicated instructions (like in
> PowerPC)? + will  the loop be vectorized?
>       C. Are speculative loads allowed? Do memory accesses trap?
>       D. More?
> 
> 2. Which transformations we want to take care of in this pass?
>    A. Conditional/unconditional loads/stores.
>    B. PHI nodes with operands that are neither constants nor SSA NAMES
> (Currently, this is not supported in tree-if-conv.c).
>    C. PHIOPT transformations (i.e., merge the PHIOPT pass into this pass
> maybe)?
>    D More?
> 3. New control-flow graphs we want to support (besides the regular
> IF_THEN_ELSE, diamond-based):
>     A. Nested diamonds.
>     B. Sequential diamonds.
>     C. More?
> 4. After we complete this pass, will the RTL-level ifcvt be needed?
>     I guess the answer is yes, but I would like to hear more opinions.
> 
> Any comments/ideas/thoughts are really appreciated.
> 
> Thanks,
> Tehila.
> 
> 

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Richard Guenther]

On 9/12/07, trevor_smigiel@playstation.sony.com
<trevor_smigiel@playstation.sony.com> wrote:
> Tehila asked me a while ago to comment based on my experience with the
> RTL if convert pass and the discussions some of us had at the GCC
> summit.  Sorry it took me so long to respond.
>
> The target I care about (Cell SPU) has some things that make an
> aggressive if convert very useful and profitable.  It has conditional
> moves for every mode (there is a single, unified register file), never
> traps on illegal addresses (addresses always wrap to the 256KB address
> space), and branches are expensive (there is no hardware cache).
>
> The main limitation with the RTL if-convert pass is that it only
> recognizes specific patterns.  It is easy to write a complicated if
> statement (just using normal C with &&/||) that would never get
> converted because it ends up with basic blocks that have many in edges
> that if-convert generally doesn't handle.   (In our internal tree we
> modified the RTL pass to handle some cases of multiple in-edges, and can
> handle any number of insns in a basic block.)
>
> I haven't looked at the tree-SSA if-convert code yet, but based on what
> was described to me at the summit it seemed to be taking the same
> approach as the RTL pass.  Recognize certain patterns and convert it.
>
> I would like to see an approach that is able to take an arbitrary flow
> graph without backedges and convert it to straight line code, limited
> only by the cost model and impossible cases (e.g., inline asm).

We now have (yet another) pass that looks at multiple basic blocks
to catch if-conversion opportunities in &&/|| sequences,
tree-ssa-ifcombine.c, which of course also handles certain special
patterns.  There is also some old patches of mine attached to PR22568
to improve RTL ifcvt to handle multi-basic-block conditional move
sequences.

Richard.

Re: [RFC] Improve Tree-SSA if-conversion - convergence of efforts

[Michael Matz]

Hi,

On Wed, 12 Sep 2007, trevor_smigiel@playstation.sony.com wrote:

> I haven't looked at the tree-SSA if-convert code yet, but based on what 
> was described to me at the summit it seemed to be taking the same 
> approach as the RTL pass.  Recognize certain patterns and convert it.
> 
> I would like to see an approach that is able to take an arbitrary flow 
> graph without backedges and convert it to straight line code, limited 
> only by the cost model and impossible cases (e.g., inline asm).
> 
> I'm not sure how that would be achieved in a target neutral way.

By extending GIMPLE to introduce conditional statements, ala:

(pred) STMT

where pred would be a boolean SSA name, with the obvious semantics.  It is 
possible that it's required to limit the forms of STMT allowed to be 
conditional.  For instance to not be stores or calls (generally no VDEFs), 
as that requires phi-nodes for the virtual ops, which would complicate our 
life pretty much, as currently phis can't be placed inside the insn 
stream.  Normal SSA names as target are no problem, as PHI nodes for those 
can be converted to simple select instructions on the same predicate.  
E.g. when we currently have this code:

if (cond) goto L2 else goto L1
L1:
  x_2 = bla
L2:
  # x_3 = PHI<x_1, x_2>
  ...

can be converted to

(cond) x_2 = bla
x_3 = (!cond) ? x_2 : x_1

It's obvious that this doesn't necessarily is profitable, as the select 
insn is a real one, whereas the PHI node only a potential insn.  Of course 
the same coalescing algorithms as in out-of-ssa can be used to make also 
the select a no-op.

With that you can generally express conditional code (with some 
limitations) as straight line code, which might enable some other 
interesting transformations.  Somewhen it has to be converted back to 
jumpy code for many machines, of course.  Depending on the machine perhaps 
even before going out-of-ssa so that some cleanups can still be done (e.g. 
merging statements under the same predicate into one basic block again, in 
case some intermediate transformations separated them from each other).


Ciao,
Michael.