[lno] [RFC] if-conversion and auto vectorizer

[Devang Patel <dpatel at apple dot com>]

We are planning to add an if-conversion pass at the tree-ssa level, that
would collapse if-then-else control flow constructs into straight line
conditional code. The primary goal of this transformation is to  
facilitate
vecorization of loops that contain if-then-else constructs (as  
described on
the vectorizer's todo list:
http://gcc.gnu.org/projects/tree-ssa/vectorization.html#cond
http://gcc.gnu.org/projects/tree-ssa/ 
vectorization.html#IdiomRecognition).

This is what we have in mind:

The if-conversion pass will transform control dependency such as this:
EXAPLE1:
      if (x > 0)
        a = y
      else
        a = z
into data dependency, such as this:
EXAMPLE2:
      a = y if (x > 0)
      a = z if !(x > 0)
The most intuitive way to express the conditional operations is with
predication, but people had already mentioned that there aren't many
tree-codes available, so adding a conditional/predicated form to a lot  
of
tree-codes would probably not be feasible. Therefore, we were planning  
to
express conditional operations using only a single new tree-code:  
SELECT.
i.e, the above code would be transformed into:
EXAMPLE3:
      c = compare (x > 0)
      a1 = y
      a2 = z
      a = select a1, a2, c

Replacing "if" statements with straight line scalar operations prior to
vectorization pass will allow the vectorizer to continue applying the
simple scheme of one-to-one replacement of scalar operations with vector
operations.

We would need to address the issues of handling such {compare/select}
sequences for architectures that have a different kind of support for
conditional code (e.g. predication, masking), probably in the RTL  
expander?

Since it is mostly intended as a preprocessing pass for the vectorizer,  
we
were thinking to apply it only to loops, and revert it if vectorization
wasn't successful (using loop versioning). Is there a benefit in trying  
to
apply this to any if-then-else in the function? it seemed to us that
applying such a transformation in the general case would be driven by
considerations that are too low level for the tree-level.

Speaking of low level - from a brief look at the current RTL level
if-conversion it seems that there isn't much potential to reuse pieces  
of
that code. Are there parts of the current RTL level if-conversion pass  
that
can be adapted to achieve the functionality we described above at tree
level?

We welcome any comments/suggestions

thanks,

Dorit and Devang.