[PATCH/RFC] PR30858 - fix vectorizer ICE

[Dorit Nuzman <DORIT at il dot ibm dot com>]

This ICE was caused by my recent fix to PR30771
(http://gcc.gnu.org/ml/gcc-patches/2007-02/msg01186.html).
In that patch, I changed the pass that marks relevant stmts to also mark
relevant phis. This is because a phi-node (that, say, defines an induction
variable) may affect the vectorization factor in the loop, and I didn't
want to have an "irrelevant" phi-node affect the vectorization factor (i.e.
a phi node that doesn't feed a computation that actually needs to be
vectorized - like array indexing).

However, I forgot that there was a reason why we did not mark phis as
relevant in the first place...:

One of the things we need to check when we detect reduction cycles, is that
intermediate values of the reduction computation are not used inside the
loop. So basically you want to know that stmts that are part of the
reduction def-use cycle have a single use inside the loop (used only by
other stmts in the reduction def-use cycle).  But I forgot that we don't
directly check the uses of these stmts; instead, what we do is the
following: a reduction stmt does not mark the defining phi-node as
relevant. This way we know that if eventually a reduction phi was marked as
relevant - it was marked by a stmt that is not a reduction - thus we can
conclude that this reduction cannot be vectorized.

So, now, with the fix to PR30771, we in fact don't check that a reduction
is properly used (or rather unused) in the loop, so we attempt to vectorize
a reduction that can't be vectorized.

There are two ways to fix this:

1) continue to rely on mark-relevant-stmts to detect whether a reduction is
used in the loop by a non-reduction stmt.
      To do this we need a way to distinguish between a phi that is used by
reduction-stmts only, and phis that are used (also) by some other stmts in
the loop. For this purpose I added another enum value for 'relevant':
"vect_used_directly_by_reduction", to identify defs that are used only by
reduction-stmts (stmts that are marked as defining a reduction) [as opposed
to the already existing enum value "vect_used_by_reduction", which
identifies defs that feed computations that end up (only) in a reduction
(i.e. these defs may be used by non-reduction stmts, but eventually, any
computations/values that are affected by these defs are used to compute a
reduction (i.e. don't get stored to memory, for example. We use that to
identify computations that we can change the order in which they are
computed)].

2) leave mark-relevant-stmts as is, and explicitly check elsewhere the uses
of the stmts that are involved in the reduction cycle.

I debated between the two approaches for a while.

The second option is more straight-forward - we explicitly check all the
uses of all the stmts in the reduction cycle - so nothing wrong can go
here. The first way is also very simple, but I worry that there may be some
more involved testcase, that I can't think of right now, that would break
it (?).

On the other hand, the second option is more expensive - with the first
scheme we get the answer "for free" (during the bottom-up scan we do
anyways).

I attach both patches. The first one was bootstrapped on i386-linux, and
the second one is being bootstrapped now on powerpc-linux. I still haven't
decided between the two, and would welcome any comments.
(by the way - the two patches together are much shorter than this email...)

(See attached file: pr30858.fix1.txt) (See attached file: pr30858.fix2.txt)

thanks,
dorit

Attachment: pr30858.fix1.txt
Description: Text document

Attachment: pr30858.fix2.txt
Description: Text document