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

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

[Robert Dewar]

> (1) MIN/MAX have better floating-point properties than conditional move.
>     Consider 
> 
>         a = 0; b = NaN;
> 
>         c = a < b ? b : a;              // 0
>     vs
>         c = a > b ? a : b;              // NaN
>     vs
>         c = max(a, b);                  // Undefined

Does the C standard really specify that the < and > here are unordered
comparisons? 

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

[Richard Henderson]

On Mon, Mar 15, 2004 at 05:42:28PM -0500, Robert Dewar wrote:
> > (1) MIN/MAX have better floating-point properties than conditional move.
> >     Consider 
> > 
> >         a = 0; b = NaN;
> > 
> >         c = a < b ? b : a;              // 0
> >     vs
> >         c = a > b ? a : b;              // NaN
> >     vs
> >         c = max(a, b);                  // Undefined
> 
> Does the C standard really specify that the < and > here are unordered
> comparisons? 

No.  C99 added isgreater etc that are defined to dtrt with NaN.

However, if fp exceptions are disabled (as they ususally are),
then the above will work as shown for almost all targets.



r~

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

[Robert Dewar]

> I might possibly agree to that for C99 (since there is a standardized
> way to accomplish the stated goal), but not for C89.

I don't understand the argument for C89. Why prevent a useful
optimization in order to enable incorrect code that just happens 
to work to keep working.

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

[Richard Henderson]

On Tue, Mar 16, 2004 at 07:27:02AM -0500, Robert Dewar wrote:
> I don't understand the argument for C89. Why prevent a useful
> optimization in order to enable incorrect code that just happens 
> to work to keep working.

For the same reasons that we preserve a set of rules that are
beyond C89 such that it's possible to write kernels.


r~

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

[Toon Moene]

Richard Henderson wrote:

> For the same reasons that we preserve a set of rules that are
> beyond C89 such that it's possible to write kernels.

Ah, I already thought so [well, actually, I was thinking "embedded 
systems"].

Can I have an option (to be set by default to "yes" by the various 
Fortran front ends) that says:

No valid (Fortran) program can cause the generation of floating point 
exceptions or memory access violations ?

Even Fortran 2003 will only allow 1.0/0.0 to cause a (legal) exception 
if you first specify:

USE IEEE_EXCEPTIONS

and the (as yet hypothetical) front end implementing that Standard could 
easily flip the switch on seeing that statement *for the translation unit*.

Thanks in advance,

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
GNU Fortran 95: http://gcc.gnu.org/fortran/ (under construction)

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

[Joseph S. Myers]

On Tue, 16 Mar 2004, Toon Moene wrote:

> Can I have an option (to be set by default to "yes" by the various 
> Fortran front ends) that says:
> 
> No valid (Fortran) program can cause the generation of floating point 
> exceptions or memory access violations ?

We have -fno-math-errno, -funsafe-math-optimizations, -ffinite-math-only,
-fno-trapping-math, -frounding-math, -fsignaling-nans (the defaults in all
cases being the opposites of these options).  I see no reason why Fortran
shouldn't change the defaults of some of these flags to values more
appropriate for Fortran (documenting this appropriately).

-- 
Joseph S. Myers
jsm@polyomino.org.uk

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

[Toon Moene]

Joseph S. Myers wrote:

> On Tue, 16 Mar 2004, Toon Moene wrote:

>>Can I have an option (to be set by default to "yes" by the various 
>>Fortran front ends) that says:
>>
>>No valid (Fortran) program can cause the generation of floating point 
>>exceptions or memory access violations ?

> We have -fno-math-errno, -funsafe-math-optimizations, -ffinite-math-only,
> -fno-trapping-math, -frounding-math, -fsignaling-nans (the defaults in all
> cases being the opposites of these options).  I see no reason why Fortran
> shouldn't change the defaults of some of these flags to values more
> appropriate for Fortran (documenting this appropriately).

Indeed, that's as far as the first problem goes.  Now the memory access 
violations (which aren't possible in bog-standard-C either, AFAICS).

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
GNU Fortran 95: http://gcc.gnu.org/fortran/ (under construction)

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

[Richard Henderson]

On Tue, Mar 16, 2004 at 11:55:59PM +0100, Toon Moene wrote:
> No valid (Fortran) program can cause the generation of floating point 
> exceptions or memory access violations ?

I think you're missing the point.  Valid Fortran programs perform
checks to see if particular operations may or should be evaluated.  E.g.

	if (y .eq. 0.) then
	  z = 0
	else
	  z = x / y
	endif

What Devang is proposing is to MOVE the test, creating (more or less)

	t1 = 0
	t2 = x / y
	if (y .eq. 0) then
	  z = t1
	else
	  z = t2
	endif

which turns a valid Fortran program into an invalid Fortran program.
Thus the concern that the transformation be suppressed when we cannot
prove that it will be safe.



r~

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

[Toon Moene]

Richard Henderson wrote:

> On Tue, Mar 16, 2004 at 11:55:59PM +0100, Toon Moene wrote:
> 
>>No valid (Fortran) program can cause the generation of floating point 
>>exceptions or memory access violations ?

> I think you're missing the point.  Valid Fortran programs perform
> checks to see if particular operations may or should be evaluated.  E.g.
> 
> 	if (y .eq. 0.) then
> 	  z = 0
> 	else
> 	  z = x / y
> 	endif
> 
> What Devang is proposing is to MOVE the test, creating (more or less)

Ah, yes, that would convert a valid Fortran program into an invalid one.

Thanks for the explanation.

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
GNU Fortran 95: http://gcc.gnu.org/fortran/ (under construction)

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

[Robert Dewar]

> However, if fp exceptions are disabled (as they ususally are),
> then the above will work as shown for almost all targets.

Yes, but they are not required to work, so the fact that they happen to
work is not a legitimate reason to avoid optimization.

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

[Richard Henderson]

On Tue, Mar 16, 2004 at 12:33:48AM -0500, Robert Dewar wrote:
> Yes, but they are not required to work, so the fact that they happen to
> work is not a legitimate reason to avoid optimization.

I might possibly agree to that for C99 (since there is a standardized
way to accomplish the stated goal), but not for C89.


r~

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

[Chris Lattner]

Richard Henderson wrote:
> This mere fact might argue for the creation of a boolean temporary for
> the comparison.

FWIW, this is exactly what we do in LLVM (all binary branches and select
instructions require a boolean argument, not a conditional).  Also,
amusingly we have a select instruction that acts exactly as was described
and even has the same name, though I do know you chose to use "COND_EXPR"
as the name in the end.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[Dorit Naishlos]

> I will also be doing the following soon (after MIN/MAX becomes gimple
> which has already be discussed and approved):

I seem to have missed the MIN/MAX discussion thread. Do you have a link to
that, or was it off the mailing list? just curious when is it planned to
add the MIN/MAX tree codes to gimple and who is responsible for that?

> But I have not thought about the if-conversions which you are asking
> for yet.

Since the ABS, MIN/MAX, etc. are special cases of the if-conversion we are
proposing, it looks like there will be an overlap between what we plan to
implement, and the transformations that will take place during phiopt,
which made us wonder whether it would make sense to implement our
transformation during phiopt as well. For example, in the case of ABS:

bb0:
      x = src[i]
      if (x < 0) GOTO BB1
            else GOTO BB2
bb1:
      x' = -x
bb2:
      x'' = PHI <x', x>
      dst[i] = x''

In the general case, the if-conversion we're proposing would transform it
into:

bb0:
      x = src[i]
      C = CMP (x < 0)
      x' = -x
      x'' = "SELECT" C, x', x
      dst[i] = x''

and in special cases (like ABS, saturation, etc) we would then (or before
hand) detect the special pattern and further optimize it as follows:

bb0:
      x = src[i]
      x'' = ABS x
      dst[i] = x''

Our main concern is that we don't know that this transformation is
desirable in the general case - we know its desirable when it enables
vectorization, but we're not sure we want to be blindly replacing
IF-THEN-ELSE's with SELECT's (or COND_EXPR) all over the place (it would
result in doing a lot of transform-IF-THEN-ELSE-into-SELECT during phiopt
followed by expand-SELECT-into-IF-THEN-ELSE during RTL expand).

Therefore, we originally thought of creating the "SELECT" patterns just
before the vectorizer, in places that are candidate for vectorization
(loops), and revert them back to if-then-else right after vectorization if
they don't get vectorized. This way, "SELECT"s will only be present after
vectorization, and only in vector form (operating on vector data types),
which is somewhat less intrusive (only passes that come after vectorization
may encounter SELECTs, and we also won't need to worry about expanding
SELECTs back to if-the-else during RTL expand).

However, considering that a lot of ifcvt functionality is going to take
place in phiopt, maybe phiopt is the right place for our ifcvt after all?
this way, there would be only one pass that performs all ifcvt-related
opts, and no danger of duplicating work (we don't want to end up
implementing a pass that will become obsolete as phiopt pass is being
enhanced). Please advise...

thanks,
Dorit and Devang



                                                                                                                                
                      Andrew Pinski                                                                                             
                      <pinskia@physics.        To:       Devang Patel <dpatel@apple.com>                                        
                      uc.edu>                  cc:       "gcc@gcc.gnu.org list" <gcc@gcc.gnu.org>, Dorit                        
                                                Naishlos/Haifa/IBM@IBMIL, Andrew Pinski <pinskia@physics.uc.edu>                
                      04/03/2004 22:12         Subject:  Re: [lno] [RFC] if-conversion and auto vectorizer                      
                                                                                                                                




There are already some if-conversions on the tree-ssa right now, they
are
called PHI OPTs and in tree-ssa-phiopt.c, I am trying to add some more
right
now but they most likely will be added to the LNO branch after an other
merge from the tree-ssa branch.

Right now on the tree-ssa the following optimization is done:
if (a == b) 1 else 0 into a == b

Right now I add the following:

if (a >= 0) a else -a into ABS (a).
if (a != b) a else b into a.

I will also be doing the following soon (after MIN/MAX becomes gimple
which has already be discussed and approved):
if (a >= b) a else b into MAX (a, b)
if (a <= b) a else b into MIN (a, b).

But I have not thought about the if-conversions which you are asking
for yet.

Thanks,
Andrew Pinski

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

[Andrew Pinski]

On Mar 14, 2004, at 03:07, Dorit Naishlos wrote:

>> I will also be doing the following soon (after MIN/MAX becomes gimple
>> which has already be discussed and approved):
>
> I seem to have missed the MIN/MAX discussion thread. Do you have a 
> link to
> that, or was it off the mailing list? just curious when is it planned 
> to
> add the MIN/MAX tree codes to gimple and who is responsible for that?

It was discussed off list (on IRC).  Really MIN/MAX is already gimple, 
just that it gets
lowered when gimplifing happens.  Also right now DOM does not 
understand MIN/MAX.
The current plan is remove the lowering when the tree-ssa gets merged 
into the mainline.
I think Daniel Berlin said he would be the one to remove the lowering 
as the linear loop
transformation generates better code with MIN/MAX instead of different 
basic blocks.
I think he also has a patch to teach DOM about it too but I am not too 
sure.

I would like to add the MIN/MAX to tree-ssa-phiopt also the idea behind 
having
MIN/MAX be "instructions" so are that more optimization opportunities 
come up from the
combine of the basic blocks, also it saves memory because of less basic 
blocks.

Thanks,
Andrew Pinski

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

[Daniel Berlin]

On Mar 14, 2004, at 2:22 PM, Andrew Pinski wrote:

>
> On Mar 14, 2004, at 03:07, Dorit Naishlos wrote:
>
>>> I will also be doing the following soon (after MIN/MAX becomes gimple
>>> which has already be discussed and approved):
>>
>> I seem to have missed the MIN/MAX discussion thread. Do you have a 
>> link to
>> that, or was it off the mailing list? just curious when is it planned 
>> to
>> add the MIN/MAX tree codes to gimple and who is responsible for that?
>
> It was discussed off list (on IRC).  Really MIN/MAX is already gimple, 
> just that it gets
> lowered when gimplifing happens.  Also right now DOM does not 
> understand MIN/MAX.
> The current plan is remove the lowering when the tree-ssa gets merged 
> into the mainline.
> I think Daniel Berlin said he would be the one to remove the lowering 
> as the linear loop
> transformation generates better code with MIN/MAX instead of different 
> basic blocks.
It's not better code so much as much less complex code.  This is in the 
case of integer min/max.
Otherwise, performing a min/max requires 1 cond_expr, two new basic 
blocks, two new labels, and two new gotos, per MAX/MIN operation.
In the case of floating point min/max, RTH pointed out that it is very 
hard to put the lowered form back together into MAX/MIN.

> I think he also has a patch to teach DOM about it too but I am not too 
> sure.
>

There isn't really much to teach DOM about here.

Previously, DOM saw

if (a < b)
	c = a;
else
	c = b;

It knew that in each arm, a was either < or > b, respectively.

With
c = MAX (a, b);

we know nothing about each arm (because they are implicit), but it 
doesn't actually matter, because you couldn't have done anything with 
the info anyway here.

So i'm not sure what you want me to teach DOM.

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

[Alex Rosenberg]

On Mar 14, 2004, at 11:22 AM, Andrew Pinski wrote:

> I would like to add the MIN/MAX to tree-ssa-phiopt also the idea 
> behind having
> MIN/MAX be "instructions" so are that more optimization opportunities 
> come up from the
> combine of the basic blocks, also it saves memory because of less 
> basic blocks.

Maybe I keep stating the obvious, but it seems to me that it would be 
better to remove the MIN/MAX nodes, in favor of the SELECT node that 
Dorit has suggested since MIN/MAX are just specific CMPs mated with a 
SELECT.

+------------------------------------------------------------+
| Alexander M. Rosenberg           <mailto:alexr@_spies.com> |
| Nobody cares what I say. Remove the underscore to mail me. |

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

[Richard Henderson]

On Sun, Mar 14, 2004 at 06:28:51PM -0800, Alex Rosenberg wrote:
> Maybe I keep stating the obvious, but it seems to me that it would be 
> better to remove the MIN/MAX nodes, in favor of the SELECT node that 
> Dorit has suggested since MIN/MAX are just specific CMPs mated with a 
> SELECT.

No.

(1) MIN/MAX have better floating-point properties than conditional move.
    Consider 

	a = 0; b = NaN;

	c = a < b ? b : a;		// 0
    vs
	c = a > b ? a : b;		// NaN
    vs
	c = max(a, b);			// Undefined

    Undefined is good because then the target md pattern doesn't have to
    be careful to preserve one or the other of the values in the face of
    unordered comparisons.

(2) I reiterate that we will NOT be adding a new SELECT node.
    The sooner Dorit changes to use COND_EXPR as I asked, the better.


r~

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

[Devang Patel]

On Mar 15, 2004, at 2:38 PM, Richard Henderson wrote:

> (2) I reiterate that we will NOT be adding a new SELECT node.
>     The sooner Dorit changes to use COND_EXPR as I asked, the better.

We keep using term SELECT because that's what we used in our discussion
earlier. But now SELECT means MODIFY_EXPR <a,COND_EXPR <c,b,d>>.
I will try to avoid using term SELECT.

In fact, that's what I used in the code snippet I included in my email
on Friday.

Concerns we have is: Do we need separate pass (which I am currently
implementing) to transform if-then-else to  use 'conditional modify 
expr'
for vectorizer or not?

OR do we replace all if-then-else during phiopts pass itself ?

We initially decided to use separate pass before vectorizer to
replace if-then-else. But at that time we did not know phiopts plans.

thoughts?
--
Devang

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

[Richard Henderson]

On Mon, Mar 15, 2004 at 03:06:56PM -0800, Devang Patel wrote:
> We keep using term SELECT because that's what we used in our discussion
> earlier. But now SELECT means MODIFY_EXPR <a,COND_EXPR <c,b,d>>.

Ok, thanks.

> Concerns we have is: Do we need separate pass (which I am currently
> implementing) to transform if-then-else to  use 'conditional modify 
> expr' for vectorizer or not?

I suspect that your vectorizer will want something much stronger than
what we will ever get from phiopts.  Phiopts is simply trying to tidy
up simple situations.

--

Something that you should watch is that COND_EXPR is *not* predication,
and you can't force it to be predication on most targets.  Depending on
what papers you're reading, this may significantly affect what you're
planning on doing.

The big distinction involves trapping expressions and operands.  E.g.

	if (test)
	   T_1 = *p;
	else
	   T_2 = 0;
	T_3 = PHI (T_1, T_2);

cannot be transformed to

	T_1 = *p;
	T_3 = test ? T_1 : 0;

unless you can show either that (1) dereferencing *p will never trap,
or (2) some other dereference of *p dominates this test.  Similar 
examples can be shown with arithmetic such as divide, or fp arithmetic
without -ffast-math (i.e. when we can't discount NaNs).



r~

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

[Devang Patel]

On Mar 15, 2004, at 3:20 PM, Richard Henderson wrote:

>> Concerns we have is: Do we need separate pass (which I am currently
>> implementing) to transform if-then-else to  use 'conditional modify
>> expr' for vectorizer or not?
>
> I suspect that your vectorizer will want something much stronger than
> what we will ever get from phiopts.  Phiopts is simply trying to tidy
> up simple situations.

Thank you. This helps to clarify things.

> --
>
> Something that you should watch is that COND_EXPR is *not* predication,
> and you can't force it to be predication on most targets.  Depending on
> what papers you're reading, this may significantly affect what you're
> planning on doing.
>
> The big distinction involves trapping expressions and operands.  E.g.
>
> 	if (test)
> 	   T_1 = *p;
> 	else
> 	   T_2 = 0;
> 	T_3 = PHI (T_1, T_2);
>
> cannot be transformed to
>
> 	T_1 = *p;
> 	T_3 = test ? T_1 : 0;
> unless you can show either that (1) dereferencing *p will never trap,
> or (2) some other dereference of *p dominates this test.  Similar
> examples can be shown with arithmetic such as divide, or fp arithmetic
> without -ffast-math (i.e. when we can't discount NaNs).

We also need to consider possible side effects of 'test' itself.

--
Devang

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

[Diego Novillo]

On Mon, 2004-03-15 at 19:01, Devang Patel wrote:

> > 	if (test)
> > 	   T_1 = *p;
> > 	else
> > 	   T_2 = 0;
> > 	T_3 = PHI (T_1, T_2);
> >
> > cannot be transformed to
> >
> > 	T_1 = *p;
> > 	T_3 = test ? T_1 : 0;
> > unless you can show either that (1) dereferencing *p will never trap,
> > or (2) some other dereference of *p dominates this test.  Similar
> > examples can be shown with arithmetic such as divide, or fp arithmetic
> > without -ffast-math (i.e. when we can't discount NaNs).
> 
> We also need to consider possible side effects of 'test' itself.
> 
Not in GIMPLE.  If 'test' is used in a predicate like the above, it
should be a GIMPLE scalar.


Diego.

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

[Richard Henderson]

On Mon, Mar 15, 2004 at 07:06:18PM -0500, Diego Novillo wrote:
> Not in GIMPLE.  If 'test' is used in a predicate like the above, it
> should be a GIMPLE scalar.

Well, *consist* of GIMPLE scalars.  According to is_gimple_condexpr
we can have "x rel-op y" as well.



r~

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

[Diego Novillo]

On Mon, 2004-03-15 at 19:45, Richard Henderson wrote:
> On Mon, Mar 15, 2004 at 07:06:18PM -0500, Diego Novillo wrote:
> > Not in GIMPLE.  If 'test' is used in a predicate like the above, it
> > should be a GIMPLE scalar.
> 
> Well, *consist* of GIMPLE scalars.  According to is_gimple_condexpr
> we can have "x rel-op y" as well.
> 
Yes.  Point being, that such a predicate can't have side effects.  Or
you only want to accept boolean scalars there?  I guess we could test
for that.


Diego.

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

[Richard Henderson]

On Mon, Mar 15, 2004 at 10:01:29PM -0500, Diego Novillo wrote:
> > Well, *consist* of GIMPLE scalars.  According to is_gimple_condexpr
> > we can have "x rel-op y" as well.
> > 
> Yes.  Point being, that such a predicate can't have side effects.  Or
> you only want to accept boolean scalars there?

Not at all.

One thing that might should be checked before marking various 
variables for ssa-renaming, however, is that you get

	if (x_1 < y_1)
	  x_2 = a, y_2 = b;
	x_3 = PHI(x_1, x_2)
	y_3 = PHI(y_1, y_2)
 ==>
	x_3 = (x_1 < y_1 ? a : x_1)
	y_3 = (x_1 < y_1 ? b : y_1)

Note that x_1 outlives the creation of x_3, which is new to 
this transformed code.  This mere fact might argue for the
creation of a boolean temporary for the comparison.


r~

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

[Devang Patel]

On Mar 15, 2004, at 7:33 PM, Richard Henderson wrote:

> One thing that might should be checked before marking various
> variables for ssa-renaming, however, is that you get
>
> 	if (x_1 < y_1)
> 	  x_2 = a, y_2 = b;
> 	x_3 = PHI(x_1, x_2)
> 	y_3 = PHI(y_1, y_2)
>  ==>
> 	x_3 = (x_1 < y_1 ? a : x_1)
> 	y_3 = (x_1 < y_1 ? b : y_1)
>
> Note that x_1 outlives the creation of x_3, which is new to
> this transformed code.  This mere fact might argue for the
> creation of a boolean temporary for the comparison.

Yes. I also need to simplify boolean exp.

--
Devang

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

[Devang Patel]

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.

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

[Andrew Pinski]

There are already some if-conversions on the tree-ssa right now, they 
are
called PHI OPTs and in tree-ssa-phiopt.c, I am trying to add some more 
right
now but they most likely will be added to the LNO branch after an other
merge from the tree-ssa branch.

Right now on the tree-ssa the following optimization is done:
if (a == b) 1 else 0 into a == b

Right now I add the following:

if (a >= 0) a else -a into ABS (a).
if (a != b) a else b into a.

I will also be doing the following soon (after MIN/MAX becomes gimple
which has already be discussed and approved):
if (a >= b) a else b into MAX (a, b)
if (a <= b) a else b into MIN (a, b).

But I have not thought about the if-conversions which you are asking 
for yet.

Thanks,
Andrew Pinski

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

[Devang Patel]

On Mar 4, 2004, at 12:12 PM, Andrew Pinski wrote:

> There are already some if-conversions on the tree-ssa right now, they 
> are
> called PHI OPTs and in tree-ssa-phiopt.c, I am trying to add some more 
> right
> now but they most likely will be added to the LNO branch after an other
> merge from the tree-ssa branch.

We looked at your patch. Briefly we discussed whether we should try to
do include it in if-conversion we are starting to implement or not.
At this point we are interested in conversion that help vectorizer.

> But I have not thought about the if-conversions which you are asking 
> for yet.

If your planning to do any transformations/optimizations that can
help auto vectorizer let us know, so that work is not overlapped.

Thanks,
--
Devang

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

[Richard Henderson]

On Thu, Mar 04, 2004 at 11:58:29AM -0800, Devang Patel wrote:
> 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

If we are going to allow such a thing at all, we'll use the exist
tree code COND_EXPR.  Jason, do you have any thoughts on adding
COND_EXPR back to GIMPLE as a conditional move?


r~

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

[Devang Patel]

On Mar 4, 2004, at 1:02 PM, Richard Henderson wrote:

> On Thu, Mar 04, 2004 at 11:58:29AM -0800, Devang Patel wrote:
>> 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
>
> If we are going to allow such a thing at all, we'll use the exist
> tree code COND_EXPR.  Jason, do you have any thoughts on adding
> COND_EXPR back to GIMPLE as a conditional move?

Only concerns I have about reusing COND_EXPR is that it may
confuse GIMPLE verifiers. And it may confuse CFG manipulators
also because what we want is to remove branches, which means
this conditional operation should not cause new additional basic
blocks.

   a = select a1, a2, c
   b = select b1, b2, c1
   c = select a1, b1, c2

We want to put all three statements in one basic block.

--
Devang

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

[Diego Novillo]

On Fri, 2004-03-05 at 14:05, Devang Patel wrote:

>    a = select a1, a2, c
>    b = select b1, b2, c1
>    c = select a1, b1, c2
> 
> We want to put all three statements in one basic block.
> 
Why would it?  They still look like a MODIFY_EXPR.

	MODIFY_EXPR <a, COND_EXPR <a1, a2, c>>
	MODIFY_EXPR <b, COND_EXPR <b1, b2, c1>>
	MODIFY_EXPR <c, COND_EXPR <a1, b1, c2>>


Diego.

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

[Diego Novillo]

On Fri, 2004-03-05 at 14:17, Diego Novillo wrote:
> On Fri, 2004-03-05 at 14:05, Devang Patel wrote:
> 
> >    a = select a1, a2, c
> >    b = select b1, b2, c1
> >    c = select a1, b1, c2
> > 
> > We want to put all three statements in one basic block.
> > 
> Why would it?  They still look like a MODIFY_EXPR.
> 
Sorry, I wasn't clear.  I meant 'Why would it confuse the optimizers?'. 
They would all be added to the same basic block and not considered
control flow alteration.


Diego.

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

[Devang Patel]

On Mar 5, 2004, at 11:17 AM, Diego Novillo wrote:

> On Fri, 2004-03-05 at 14:05, Devang Patel wrote:
>
>>    a = select a1, a2, c
>>    b = select b1, b2, c1
>>    c = select a1, b1, c2
>>
>> We want to put all three statements in one basic block.
>>
> Why would it?  They still look like a MODIFY_EXPR.
>
> 	MODIFY_EXPR <a, COND_EXPR <a1, a2, c>>
> 	MODIFY_EXPR <b, COND_EXPR <b1, b2, c1>>
> 	MODIFY_EXPR <c, COND_EXPR <a1, b1, c2>>

My worry is it would it cause confusion to gimple verifiers?
Would it be possible that during verification this is flagged
as non gimple expression ? If not and CFG routines want alter
control flow when they see it then its fine. I do not know
if someone else will be tickled by COND_EXPR or not.

But so far it seems that's not the case.

Thanks,
--
Devang

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

[Diego Novillo]

On Fri, 2004-03-05 at 14:27, Devang Patel wrote:

> My worry is it would it cause confusion to gimple verifiers?
> Would it be possible that during verification this is flagged
> as non gimple expression ? If not and CFG routines want alter
> control flow when they see it then its fine. I do not know
> if someone else will be tickled by COND_EXPR or not.
> 
We just have to add the right bits in the GIMPLE grammar.  We will need
to define exactly what kind of arguments we want to allow.  In
principle, I'd say that we would do something like

	cond-assign : MODIFY_EXPR
			op0 -> is_gimple_min_lval
			op1 -> cond-assign-rhs
	cond-assign-rhs : COND_EXPR
			op0 -> is_gimple_condexpr
			op1 -> is_gimple_val


Diego.

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

[Diego Novillo]

On Fri, 2004-03-05 at 14:42, Diego Novillo wrote:

> 	cond-assign : MODIFY_EXPR
> 			op0 -> is_gimple_min_lval
> 			op1 -> cond-assign-rhs
> 	cond-assign-rhs : COND_EXPR
> 			op0 -> is_gimple_condexpr
> 			op1 -> is_gimple_val
			  op2 -> is_gimple_val

Not my day.  Sorry.

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

[Devang Patel]

[-- Attachment #1: Type: text/plain, Size: 2376 bytes --]

OK. So far I have coded transformation to transform

bar ()
{
   int A[N+1], B[N+1], C[N+1], D[N+1];
   int i;

   for (i = 1; i<N; i++)
     {
       if (A[i] > 0)
         {
           A[i] = A[i] + C[i];
           B[i] = A[i] + 1;
         }
       else
         {
           A[i] = D[i];
           B[i] = D[i] + 1;
         }
     }
   ibar(A);
   ibar(B);
}

into :

bar ()
{
   int i;
   int D[17];
   int C[17];
   int B[17];
   int A[17];
   int T.5;
   int T.4;
   int T.3;
   int T.2;
   int T.1;
   int T.0;

   # BLOCK 0
   # PRED: ENTRY [100.0%]  (fallthru,exec)
   # SUCC: 1 [100.0%]  (fallthru,exec)

   # BLOCK 1
   # PRED: 6 [100.0%]  (fallthru) 0 [100.0%]  (fallthru,exec)
   # i_1 = PHI <1(0), i_15(6)>;
<L0>:;
   T.0_3 = if (1)
     {
       A[i_1];
     };
   if (T.0_3 > 0) goto <L1>; else goto <L2>;
   # SUCC: 3 [21.0%]  (false,exec) 2 [79.0%]  (true,exec)

   # BLOCK 2
   # PRED: 1 [79.0%]  (true,exec)
<L1>:;
   T.1_9 = if (1 && T.0_3 > 0)
     {
       C[i_1];
     };
   T.2_10 = if (1 && T.0_3 > 0)
     {
       T.0_3 + T.1_9;
     };
   A[i_1] = if (1 && T.0_3 > 0)
     {
       T.2_10
     };
   T.3_12 = if (1 && T.0_3 > 0)
     {
       T.2_10 + 1;
     };
   B[i_1] = if (1 && T.0_3 > 0)
     {
       T.3_12
     };
   goto <bb 4> (<L3>);
   # SUCC: 4 [100.0%]  (fallthru,exec)

   # BLOCK 3
   # PRED: 1 [21.0%]  (false,exec)
<L2>:;
   T.4_5 = if (1 && !(T.0_3 > 0))
     {
       D[i_1];
     };
   A[i_1] = if (1 && !(T.0_3 > 0))
     {
       T.4_5
     };
   T.5_7 = if (1 && !(T.0_3 > 0))
     {
       T.4_5 + 1;
     };
   B[i_1] = if (1 && !(T.0_3 > 0))
     {
       T.5_7
     };
   # SUCC: 4 [100.0%]  (fallthru,exec)

   # BLOCK 4
   # PRED: 3 [100.0%]  (fallthru,exec) 2 [100.0%]  (fallthru,exec)
<L3>:;
   i_15 = i_1 + 1;
   if (i_15 <= 15) goto <L8>; else goto <L5>;
   # SUCC: 5 [11.0%]  (false,exec) 6 [89.0%]  (true,exec)

   # BLOCK 6
   # PRED: 4 [89.0%]  (true,exec)
<L8>:;
   goto <bb 1> (<L0>);
   # SUCC: 1 [100.0%]  (fallthru)

   # BLOCK 5
   # PRED: 4 [11.0%]  (false,exec)
<L5>:;
   ibar (&A);
   ibar (&B);
   return;
   # SUCC: EXIT [100.0%]

}

I spent lot of time unnecessary to create super block inside loop by
merging block 2 and 3 into block 1.

If vectorizer can not vectorize this loop then it will be reverted to
original form using loop versioning. Am I on the right track ?

Thanks,
--
Devang


[-- Attachment #2: tree_if_conv.ver_0.diff.gz --]
[-- Type: application/x-gzip, Size: 4637 bytes --]

[-- Attachment #3: Type: text/plain, Size: 1 bytes --]

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

[Zdenek Dvorak]

Hello,

> OK. So far I have coded transformation to transform
> 
> bar ()
> {
>   int A[N+1], B[N+1], C[N+1], D[N+1];
>   int i;
> 
>   for (i = 1; i<N; i++)
>     {
>       if (A[i] > 0)
>         {
>           A[i] = A[i] + C[i];
>           B[i] = A[i] + 1;
>         }
>       else
>         {
>           A[i] = D[i];
>           B[i] = D[i] + 1;
>         }
>     }
>   ibar(A);
>   ibar(B);
> }
> 
> into :
> 
> bar ()
> {
>   int i;
>   int D[17];
>   int C[17];
>   int B[17];
>   int A[17];
>   int T.5;
>   int T.4;
>   int T.3;
>   int T.2;
>   int T.1;
>   int T.0;
> 
>   # BLOCK 0
>   # PRED: ENTRY [100.0%]  (fallthru,exec)
>   # SUCC: 1 [100.0%]  (fallthru,exec)
> 
>   # BLOCK 1
>   # PRED: 6 [100.0%]  (fallthru) 0 [100.0%]  (fallthru,exec)
>   # i_1 = PHI <1(0), i_15(6)>;
> <L0>:;
>   T.0_3 = if (1)
>     {
>       A[i_1];
>     };
>   if (T.0_3 > 0) goto <L1>; else goto <L2>;
>   # SUCC: 3 [21.0%]  (false,exec) 2 [79.0%]  (true,exec)
> 
>   # BLOCK 2
>   # PRED: 1 [79.0%]  (true,exec)
> <L1>:;
>   T.1_9 = if (1 && T.0_3 > 0)

why this "1 &&" part?

>     {
>       C[i_1];
>     };
>   T.2_10 = if (1 && T.0_3 > 0)
>     {
>       T.0_3 + T.1_9;
>     };
>   A[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.2_10
>     };
>   T.3_12 = if (1 && T.0_3 > 0)
>     {
>       T.2_10 + 1;
>     };
>   B[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.3_12
>     };
>   goto <bb 4> (<L3>);
>   # SUCC: 4 [100.0%]  (fallthru,exec)
> 
>   # BLOCK 3
>   # PRED: 1 [21.0%]  (false,exec)
> <L2>:;
>   T.4_5 = if (1 && !(T.0_3 > 0))
>     {
>       D[i_1];
>     };
>   A[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5
>     };
>   T.5_7 = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5 + 1;
>     };
>   B[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.5_7
>     };
>   # SUCC: 4 [100.0%]  (fallthru,exec)
> 
>   # BLOCK 4
>   # PRED: 3 [100.0%]  (fallthru,exec) 2 [100.0%]  (fallthru,exec)
> <L3>:;
>   i_15 = i_1 + 1;
>   if (i_15 <= 15) goto <L8>; else goto <L5>;
>   # SUCC: 5 [11.0%]  (false,exec) 6 [89.0%]  (true,exec)
> 
>   # BLOCK 6
>   # PRED: 4 [89.0%]  (true,exec)
> <L8>:;
>   goto <bb 1> (<L0>);
>   # SUCC: 1 [100.0%]  (fallthru)
> 
>   # BLOCK 5
>   # PRED: 4 [11.0%]  (false,exec)
> <L5>:;
>   ibar (&A);
>   ibar (&B);
>   return;
>   # SUCC: EXIT [100.0%]
> 
> }
> 
> I spent lot of time unnecessary to create super block inside loop by
> merging block 2 and 3 into block 1.
> 
> If vectorizer can not vectorize this loop then it will be reverted to
> original form using loop versioning. Am I on the right track ?

I am not at all sure what you want to achieve with this transformation;
it seems to me that you haven't done anything that could possibly make
vectorizer's work easier.

Zdenek

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

[Devang Patel]

On Mar 13, 2004, at 1:24 AM, Zdenek Dvorak wrote:

[snip]

>>   # BLOCK 2
>>   # PRED: 1 [79.0%]  (true,exec)
>> <L1>:;
>>   T.1_9 = if (1 && T.0_3 > 0)
>
> why this "1 &&" part?

Its because, I have not simplified conditional boolean expressions yet.

[snip]

>>
>> I spent lot of time unnecessary to create super block inside loop by
>> merging block 2 and 3 into block 1.
>>
>> If vectorizer can not vectorize this loop then it will be reverted to
>> original form using loop versioning. Am I on the right track ?
>
> I am not at all sure what you want to achieve with this transformation;
> it seems to me that you haven't done anything that could possibly make
> vectorizer's work easier.

After transforming statements, I should be able to merge all blocks
in one super block inside loop. Once that is done vectorizer just needs
to do one-to-one replacement.

--
Devang

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

[Dorit Naishlos]

> I am not at all sure what you want to achieve with this transformation;
> it seems to me that you haven't done anything that could possibly make
> vectorizer's work easier.

I think Devang's example showed an intermediate stage in the development of
the transformation. The final goal of the transformation is to transform a
multi-block loop like the following:

LOOP:
      if (A[i] > 0)
         {
           A[i] = A[i] + C[i];
           B[i] = A[i] + 1;
         }
       else
         {
           A[i] = D[i];
         }

into straight-line single block loop:

LOOP:
[1]   C = CMP A[i] > 0
[2]   A_then = A[i] + c[i]
[3]   A[i] = "SELECT" C ? A_then : A[i]
[4]   B_then = A[i] + 1
[5]   B[i] = "SELECT" C ? B_then : B[i]
[6]   A_else = D[i]
[7]   A[i] = "SELECT" ^C ? A_else : A[i]

[3]&[7] would be merged (by an additional pass, or directly) to obtain the
following optimized code:

LOOP:
[1]   C = CMP A[i] > 0
[2]   A_then = A[i] + c[i]
[3]   B_then = A[i] + 1
[4]   B[i] = "SELECT" C ? B_then : B[i]
[5]   A_else = D[i]
[6]   A[i] = "SELECT" C ? A_then : A_else

(This is also where special idioms like saturation, would be recognized.)

dorit




                                                                                                                                      
                      Zdenek Dvorak                                                                                                   
                      <rakdver@atrey.karlin.m        To:       Devang Patel <dpatel@apple.com>                                        
                      ff.cuni.cz>                    cc:       "gcc@gcc.gnu.org list" <gcc@gcc.gnu.org>, Jason Merrill                
                                                      <jason@redhat.com>, Dorit Naishlos/Haifa/IBM@IBMIL, Richard Henderson           
                      13/03/2004 11:24                <rth@redhat.com>, Diego Novillo <dnovillo@redhat.com>                           
                                                     Subject:  Re: [lno] [RFC] if-conversion and auto vectorizer                      
                                                                                                                                      




Hello,

> OK. So far I have coded transformation to transform
>
> bar ()
> {
>   int A[N+1], B[N+1], C[N+1], D[N+1];
>   int i;
>
>   for (i = 1; i<N; i++)
>     {
>       if (A[i] > 0)
>         {
>           A[i] = A[i] + C[i];
>           B[i] = A[i] + 1;
>         }
>       else
>         {
>           A[i] = D[i];
>           B[i] = D[i] + 1;
>         }
>     }
>   ibar(A);
>   ibar(B);
> }
>
> into :
>
> bar ()
> {
>   int i;
>   int D[17];
>   int C[17];
>   int B[17];
>   int A[17];
>   int T.5;
>   int T.4;
>   int T.3;
>   int T.2;
>   int T.1;
>   int T.0;
>
>   # BLOCK 0
>   # PRED: ENTRY [100.0%]  (fallthru,exec)
>   # SUCC: 1 [100.0%]  (fallthru,exec)
>
>   # BLOCK 1
>   # PRED: 6 [100.0%]  (fallthru) 0 [100.0%]  (fallthru,exec)
>   # i_1 = PHI <1(0), i_15(6)>;
> <L0>:;
>   T.0_3 = if (1)
>     {
>       A[i_1];
>     };
>   if (T.0_3 > 0) goto <L1>; else goto <L2>;
>   # SUCC: 3 [21.0%]  (false,exec) 2 [79.0%]  (true,exec)
>
>   # BLOCK 2
>   # PRED: 1 [79.0%]  (true,exec)
> <L1>:;
>   T.1_9 = if (1 && T.0_3 > 0)

why this "1 &&" part?

>     {
>       C[i_1];
>     };
>   T.2_10 = if (1 && T.0_3 > 0)
>     {
>       T.0_3 + T.1_9;
>     };
>   A[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.2_10
>     };
>   T.3_12 = if (1 && T.0_3 > 0)
>     {
>       T.2_10 + 1;
>     };
>   B[i_1] = if (1 && T.0_3 > 0)
>     {
>       T.3_12
>     };
>   goto <bb 4> (<L3>);
>   # SUCC: 4 [100.0%]  (fallthru,exec)
>
>   # BLOCK 3
>   # PRED: 1 [21.0%]  (false,exec)
> <L2>:;
>   T.4_5 = if (1 && !(T.0_3 > 0))
>     {
>       D[i_1];
>     };
>   A[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5
>     };
>   T.5_7 = if (1 && !(T.0_3 > 0))
>     {
>       T.4_5 + 1;
>     };
>   B[i_1] = if (1 && !(T.0_3 > 0))
>     {
>       T.5_7
>     };
>   # SUCC: 4 [100.0%]  (fallthru,exec)
>
>   # BLOCK 4
>   # PRED: 3 [100.0%]  (fallthru,exec) 2 [100.0%]  (fallthru,exec)
> <L3>:;
>   i_15 = i_1 + 1;
>   if (i_15 <= 15) goto <L8>; else goto <L5>;
>   # SUCC: 5 [11.0%]  (false,exec) 6 [89.0%]  (true,exec)
>
>   # BLOCK 6
>   # PRED: 4 [89.0%]  (true,exec)
> <L8>:;
>   goto <bb 1> (<L0>);
>   # SUCC: 1 [100.0%]  (fallthru)
>
>   # BLOCK 5
>   # PRED: 4 [11.0%]  (false,exec)
> <L5>:;
>   ibar (&A);
>   ibar (&B);
>   return;
>   # SUCC: EXIT [100.0%]
>
> }
>
> I spent lot of time unnecessary to create super block inside loop by
> merging block 2 and 3 into block 1.
>
> If vectorizer can not vectorize this loop then it will be reverted to
> original form using loop versioning. Am I on the right track ?

I am not at all sure what you want to achieve with this transformation;
it seems to me that you haven't done anything that could possibly make
vectorizer's work easier.

Zdenek