* Fw: [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-14 10:57 Dorit Naishlos
2004-03-14 19:22 ` Andrew Pinski
0 siblings, 1 reply; 39+ messages in thread
From: Dorit Naishlos @ 2004-03-14 10:57 UTC (permalink / raw)
To: Andrew Pinski; +Cc: gcc, Devang Patel
> 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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-14 10:57 Fw: [lno] [RFC] if-conversion and auto vectorizer Dorit Naishlos
@ 2004-03-14 19:22 ` Andrew Pinski
2004-03-14 22:31 ` Daniel Berlin
2004-03-15 2:29 ` Alex Rosenberg
0 siblings, 2 replies; 39+ messages in thread
From: Andrew Pinski @ 2004-03-14 19:22 UTC (permalink / raw)
To: Dorit Naishlos; +Cc: gcc, Devang Patel, 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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-14 19:22 ` Andrew Pinski
@ 2004-03-14 22:31 ` Daniel Berlin
2004-03-15 2:29 ` Alex Rosenberg
1 sibling, 0 replies; 39+ messages in thread
From: Daniel Berlin @ 2004-03-14 22:31 UTC (permalink / raw)
To: Andrew Pinski; +Cc: gcc, Dorit Naishlos, Devang Patel
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-14 19:22 ` Andrew Pinski
2004-03-14 22:31 ` Daniel Berlin
@ 2004-03-15 2:29 ` Alex Rosenberg
2004-03-15 22:38 ` Richard Henderson
1 sibling, 1 reply; 39+ messages in thread
From: Alex Rosenberg @ 2004-03-15 2:29 UTC (permalink / raw)
To: egcs
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. |
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-15 2:29 ` Alex Rosenberg
@ 2004-03-15 22:38 ` Richard Henderson
2004-03-15 23:08 ` Devang Patel
0 siblings, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-15 22:38 UTC (permalink / raw)
To: Alex Rosenberg; +Cc: gcc
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-15 22:38 ` Richard Henderson
@ 2004-03-15 23:08 ` Devang Patel
2004-03-15 23:20 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Devang Patel @ 2004-03-15 23:08 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc@gcc.gnu.org list
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-15 23:08 ` Devang Patel
@ 2004-03-15 23:20 ` Richard Henderson
2004-03-16 0:02 ` Devang Patel
0 siblings, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-15 23:20 UTC (permalink / raw)
To: Devang Patel; +Cc: gcc@gcc.gnu.org list
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-15 23:20 ` Richard Henderson
@ 2004-03-16 0:02 ` Devang Patel
2004-03-16 0:07 ` Diego Novillo
0 siblings, 1 reply; 39+ messages in thread
From: Devang Patel @ 2004-03-16 0:02 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc@gcc.gnu.org list
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 0:02 ` Devang Patel
@ 2004-03-16 0:07 ` Diego Novillo
2004-03-16 0:45 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Diego Novillo @ 2004-03-16 0:07 UTC (permalink / raw)
To: Devang Patel; +Cc: Richard Henderson, gcc@gcc.gnu.org list
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 0:07 ` Diego Novillo
@ 2004-03-16 0:45 ` Richard Henderson
2004-03-16 3:02 ` Diego Novillo
0 siblings, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-16 0:45 UTC (permalink / raw)
To: Diego Novillo; +Cc: Devang Patel, gcc@gcc.gnu.org list
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 0:45 ` Richard Henderson
@ 2004-03-16 3:02 ` Diego Novillo
2004-03-16 3:33 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Diego Novillo @ 2004-03-16 3:02 UTC (permalink / raw)
To: Richard Henderson; +Cc: Devang Patel, gcc@gcc.gnu.org list
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 3:02 ` Diego Novillo
@ 2004-03-16 3:33 ` Richard Henderson
2004-03-16 6:33 ` Devang Patel
0 siblings, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-16 3:33 UTC (permalink / raw)
To: Diego Novillo; +Cc: Devang Patel, gcc@gcc.gnu.org list
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 3:33 ` Richard Henderson
@ 2004-03-16 6:33 ` Devang Patel
0 siblings, 0 replies; 39+ messages in thread
From: Devang Patel @ 2004-03-16 6:33 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc@gcc.gnu.org list, Diego Novillo
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-16 12:27 Robert Dewar
2004-03-16 18:32 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Robert Dewar @ 2004-03-16 12:27 UTC (permalink / raw)
To: dewar, rth; +Cc: alexr, gcc
> 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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 12:27 Robert Dewar
@ 2004-03-16 18:32 ` Richard Henderson
2004-03-16 22:51 ` Toon Moene
0 siblings, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-16 18:32 UTC (permalink / raw)
To: Robert Dewar; +Cc: alexr, gcc
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 18:32 ` Richard Henderson
@ 2004-03-16 22:51 ` Toon Moene
2004-03-16 23:10 ` Joseph S. Myers
2004-03-16 23:37 ` Richard Henderson
0 siblings, 2 replies; 39+ messages in thread
From: Toon Moene @ 2004-03-16 22:51 UTC (permalink / raw)
To: Richard Henderson; +Cc: Robert Dewar, alexr, gcc
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)
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 22:51 ` Toon Moene
@ 2004-03-16 23:10 ` Joseph S. Myers
2004-03-16 23:28 ` Toon Moene
2004-03-16 23:37 ` Richard Henderson
1 sibling, 1 reply; 39+ messages in thread
From: Joseph S. Myers @ 2004-03-16 23:10 UTC (permalink / raw)
To: Toon Moene; +Cc: Richard Henderson, Robert Dewar, alexr, gcc
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 23:10 ` Joseph S. Myers
@ 2004-03-16 23:28 ` Toon Moene
0 siblings, 0 replies; 39+ messages in thread
From: Toon Moene @ 2004-03-16 23:28 UTC (permalink / raw)
To: Joseph S. Myers; +Cc: Richard Henderson, Robert Dewar, alexr, gcc
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)
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 22:51 ` Toon Moene
2004-03-16 23:10 ` Joseph S. Myers
@ 2004-03-16 23:37 ` Richard Henderson
2004-03-16 23:42 ` Toon Moene
1 sibling, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-16 23:37 UTC (permalink / raw)
To: Toon Moene; +Cc: Robert Dewar, alexr, gcc
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 23:37 ` Richard Henderson
@ 2004-03-16 23:42 ` Toon Moene
0 siblings, 0 replies; 39+ messages in thread
From: Toon Moene @ 2004-03-16 23:42 UTC (permalink / raw)
To: Richard Henderson; +Cc: Robert Dewar, alexr, gcc
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)
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-16 5:33 Robert Dewar
2004-03-16 6:54 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Robert Dewar @ 2004-03-16 5:33 UTC (permalink / raw)
To: dewar, rth; +Cc: alexr, gcc
> 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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-16 5:33 Robert Dewar
@ 2004-03-16 6:54 ` Richard Henderson
0 siblings, 0 replies; 39+ messages in thread
From: Richard Henderson @ 2004-03-16 6:54 UTC (permalink / raw)
To: Robert Dewar; +Cc: alexr, gcc
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-16 3:46 Chris Lattner
0 siblings, 0 replies; 39+ messages in thread
From: Chris Lattner @ 2004-03-16 3:46 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc, Diego Novillo, Devang Patel
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/
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-15 22:42 Robert Dewar
2004-03-15 23:08 ` Richard Henderson
0 siblings, 1 reply; 39+ messages in thread
From: Robert Dewar @ 2004-03-15 22:42 UTC (permalink / raw)
To: alexr, rth; +Cc: gcc
> (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?
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-15 22:42 Robert Dewar
@ 2004-03-15 23:08 ` Richard Henderson
0 siblings, 0 replies; 39+ messages in thread
From: Richard Henderson @ 2004-03-15 23:08 UTC (permalink / raw)
To: Robert Dewar; +Cc: alexr, gcc
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* [lno] [RFC] if-conversion and auto vectorizer
@ 2004-03-04 19:59 Devang Patel
2004-03-04 20:12 ` Andrew Pinski
2004-03-04 21:03 ` Richard Henderson
0 siblings, 2 replies; 39+ messages in thread
From: Devang Patel @ 2004-03-04 19:59 UTC (permalink / raw)
To: gcc@gcc.gnu.org list; +Cc: Dorit Naishlos
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-04 19:59 Devang Patel
@ 2004-03-04 20:12 ` Andrew Pinski
2004-03-04 20:39 ` Devang Patel
2004-03-04 21:03 ` Richard Henderson
1 sibling, 1 reply; 39+ messages in thread
From: Andrew Pinski @ 2004-03-04 20:12 UTC (permalink / raw)
To: Devang Patel; +Cc: gcc@gcc.gnu.org list, Dorit Naishlos, 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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-04 20:12 ` Andrew Pinski
@ 2004-03-04 20:39 ` Devang Patel
0 siblings, 0 replies; 39+ messages in thread
From: Devang Patel @ 2004-03-04 20:39 UTC (permalink / raw)
To: Andrew Pinski; +Cc: gcc@gcc.gnu.org list, Dorit Naishlos
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-04 19:59 Devang Patel
2004-03-04 20:12 ` Andrew Pinski
@ 2004-03-04 21:03 ` Richard Henderson
2004-03-05 19:06 ` Devang Patel
1 sibling, 1 reply; 39+ messages in thread
From: Richard Henderson @ 2004-03-04 21:03 UTC (permalink / raw)
To: Devang Patel; +Cc: gcc@gcc.gnu.org list, Dorit Naishlos, Jason Merrill
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~
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-04 21:03 ` Richard Henderson
@ 2004-03-05 19:06 ` Devang Patel
2004-03-05 19:17 ` Diego Novillo
0 siblings, 1 reply; 39+ messages in thread
From: Devang Patel @ 2004-03-05 19:06 UTC (permalink / raw)
To: Richard Henderson; +Cc: gcc@gcc.gnu.org list, Dorit Naishlos, Jason Merrill
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:06 ` Devang Patel
@ 2004-03-05 19:17 ` Diego Novillo
2004-03-05 19:22 ` Diego Novillo
2004-03-05 19:28 ` Devang Patel
0 siblings, 2 replies; 39+ messages in thread
From: Diego Novillo @ 2004-03-05 19:17 UTC (permalink / raw)
To: Devang Patel
Cc: Richard Henderson, gcc@gcc.gnu.org list, Dorit Naishlos, Jason Merrill
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:17 ` Diego Novillo
@ 2004-03-05 19:22 ` Diego Novillo
2004-03-05 19:28 ` Devang Patel
1 sibling, 0 replies; 39+ messages in thread
From: Diego Novillo @ 2004-03-05 19:22 UTC (permalink / raw)
To: Devang Patel
Cc: Richard Henderson, gcc@gcc.gnu.org list, Dorit Naishlos, Jason Merrill
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:17 ` Diego Novillo
2004-03-05 19:22 ` Diego Novillo
@ 2004-03-05 19:28 ` Devang Patel
2004-03-05 19:41 ` Diego Novillo
1 sibling, 1 reply; 39+ messages in thread
From: Devang Patel @ 2004-03-05 19:28 UTC (permalink / raw)
To: Diego Novillo
Cc: gcc@gcc.gnu.org list, Dorit Naishlos, Richard Henderson, Jason Merrill
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:28 ` Devang Patel
@ 2004-03-05 19:41 ` Diego Novillo
2004-03-05 19:44 ` Diego Novillo
0 siblings, 1 reply; 39+ messages in thread
From: Diego Novillo @ 2004-03-05 19:41 UTC (permalink / raw)
To: Devang Patel
Cc: gcc@gcc.gnu.org list, Dorit Naishlos, Richard Henderson, Jason Merrill
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:41 ` Diego Novillo
@ 2004-03-05 19:44 ` Diego Novillo
2004-03-12 18:45 ` Devang Patel
0 siblings, 1 reply; 39+ messages in thread
From: Diego Novillo @ 2004-03-05 19:44 UTC (permalink / raw)
To: Devang Patel
Cc: gcc@gcc.gnu.org list, Dorit Naishlos, Richard Henderson, Jason Merrill
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.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-05 19:44 ` Diego Novillo
@ 2004-03-12 18:45 ` Devang Patel
2004-03-13 9:24 ` Zdenek Dvorak
0 siblings, 1 reply; 39+ messages in thread
From: Devang Patel @ 2004-03-12 18:45 UTC (permalink / raw)
To: gcc@gcc.gnu.org list
Cc: Jason Merrill, Dorit Naishlos, Richard Henderson, Diego Novillo
[-- 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 --]
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-12 18:45 ` Devang Patel
@ 2004-03-13 9:24 ` Zdenek Dvorak
2004-03-13 22:41 ` Devang Patel
2004-03-14 10:59 ` Dorit Naishlos
0 siblings, 2 replies; 39+ messages in thread
From: Zdenek Dvorak @ 2004-03-13 9:24 UTC (permalink / raw)
To: Devang Patel
Cc: gcc@gcc.gnu.org list, Jason Merrill, Dorit Naishlos,
Richard Henderson, Diego Novillo
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-13 9:24 ` Zdenek Dvorak
@ 2004-03-13 22:41 ` Devang Patel
2004-03-14 10:59 ` Dorit Naishlos
1 sibling, 0 replies; 39+ messages in thread
From: Devang Patel @ 2004-03-13 22:41 UTC (permalink / raw)
To: Zdenek Dvorak
Cc: gcc@gcc.gnu.org list, Jason Merrill, Richard Henderson,
Dorit Naishlos, Diego Novillo
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
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [lno] [RFC] if-conversion and auto vectorizer
2004-03-13 9:24 ` Zdenek Dvorak
2004-03-13 22:41 ` Devang Patel
@ 2004-03-14 10:59 ` Dorit Naishlos
1 sibling, 0 replies; 39+ messages in thread
From: Dorit Naishlos @ 2004-03-14 10:59 UTC (permalink / raw)
To: Zdenek Dvorak; +Cc: gcc@gcc.gnu.org list, Devang Patel
> 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
^ permalink raw reply [flat|nested] 39+ messages in thread
end of thread, other threads:[~2004-03-16 23:37 UTC | newest]
Thread overview: 39+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-03-14 10:57 Fw: [lno] [RFC] if-conversion and auto vectorizer Dorit Naishlos
2004-03-14 19:22 ` Andrew Pinski
2004-03-14 22:31 ` Daniel Berlin
2004-03-15 2:29 ` Alex Rosenberg
2004-03-15 22:38 ` Richard Henderson
2004-03-15 23:08 ` Devang Patel
2004-03-15 23:20 ` Richard Henderson
2004-03-16 0:02 ` Devang Patel
2004-03-16 0:07 ` Diego Novillo
2004-03-16 0:45 ` Richard Henderson
2004-03-16 3:02 ` Diego Novillo
2004-03-16 3:33 ` Richard Henderson
2004-03-16 6:33 ` Devang Patel
-- strict thread matches above, loose matches on Subject: below --
2004-03-16 12:27 Robert Dewar
2004-03-16 18:32 ` Richard Henderson
2004-03-16 22:51 ` Toon Moene
2004-03-16 23:10 ` Joseph S. Myers
2004-03-16 23:28 ` Toon Moene
2004-03-16 23:37 ` Richard Henderson
2004-03-16 23:42 ` Toon Moene
2004-03-16 5:33 Robert Dewar
2004-03-16 6:54 ` Richard Henderson
2004-03-16 3:46 Chris Lattner
2004-03-15 22:42 Robert Dewar
2004-03-15 23:08 ` Richard Henderson
2004-03-04 19:59 Devang Patel
2004-03-04 20:12 ` Andrew Pinski
2004-03-04 20:39 ` Devang Patel
2004-03-04 21:03 ` Richard Henderson
2004-03-05 19:06 ` Devang Patel
2004-03-05 19:17 ` Diego Novillo
2004-03-05 19:22 ` Diego Novillo
2004-03-05 19:28 ` Devang Patel
2004-03-05 19:41 ` Diego Novillo
2004-03-05 19:44 ` Diego Novillo
2004-03-12 18:45 ` Devang Patel
2004-03-13 9:24 ` Zdenek Dvorak
2004-03-13 22:41 ` Devang Patel
2004-03-14 10:59 ` Dorit Naishlos
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).