Re: Serious performance regression -- some tree optimizer questions

[Ulrich Weigand <Ulrich dot Weigand at de dot ibm dot com>]

Michael Matz <matz@suse.de> wrote on 12/19/2004 01:21:04 AM:

> Perhaps you can try the attached patch.  It is against a slightly older
> version of HEAD, but fixes some ugly regression with ivopts on ppc64, and
> in particular also helps a bit with the 32-bit index arithmetic.  Zdenek
> is in the process of splitting it up and submitting it for HEAD.

It helps a bit, but unfortunately not significantly (for the mgrid resid
hot spot, at least).  It does recognize now that in the
  DO I1=2,N-1
loop both I1 and I1-1 cannot overflow.  However it does not recognize that
I1+1 cannot overflow (and hence it doesn't combine the induction variables
as it would be necessary).

The problem is that this is not just an inadequacy of the current code,
it is a fundamental problem:  you *cannot* deduce I1+1 doesn't overflow
because it is simply not *true* that it is a logical consequence of all
known facts.  In theory, I1+1 could overflow for the initial value of
N == INT_MIN; and at the level of the GENERIC tree passed to the
mid-end, there is nothing that allows to conclude that this case
cannot happen ...

This is why I would suggest that we finally do make use of the fact that
signed overflow represents undefined behaviour in some languages.  We
couldn't at the RTL level because there is no reliable way to distinguish
between signed and unsigned arithmetic there.  But at the tree level,
if the induction step is performed using arithmetic on a signed data
type, and neither -fwrapv nor -ftrapv is in effect, we could simply
allow the scalar evolution mechanism to conclude that this variable
does not overflow.

What do you think?

Bye,
Ulrich
--
  Dr. Ulrich Weigand
  Linux for S/390 Design & Development
  IBM Deutschland Entwicklung GmbH, Schoenaicher Str. 220, 71032 Boeblingen
  Phone: +49-7031/16-3727   ---   Email: Ulrich.Weigand@de.ibm.com