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

[Tehila Meyzels <TEHILA@il.ibm.com>]

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.