This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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:

2. If -conversion for multiple IF_THEN_ELSE clauses, by Victor Kaplansky:
Also mentioned here:

3.  (unconditional) Store sinking (4.1.1 based), by Revital Eres and Victor
Kaplansky: (same patch as
Also mentioned here:

4. Conditional load hoisting (4.1.1 based), by myself:

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
    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
      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
   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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]