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

[Michael Matz <matz@suse.de>]

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.