Re: Add overflow infinity handling to VRP

[Ian Lance Taylor <iant at google dot com>]

Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz> writes:

> > Moreover, it's not really accurate to imply that VRP currently models
> > signed overflow as saturation.  VRP currently does not distinguish
> > TYPE_MAX from an overflow value.  That is not the same as saturating,
> > because VRP also uses TYPE_MAX to represent values that increase
> > steadily during loops.
> 
> what exactly is the difference between saturation and the current
> behavior?  If I understand things correctly, saturation is exactly
> what we do now -- replacing everything larger than MAX by MAX, and
> not further treating the value in any special way.

That is how VRP handles arithmetic overflow.  But VRP also uses
TYPE_MAX in a different way.  As VRP simulates execution of a loop, it
will see that a variable is being incremented.  Rather than simulate
execution of the loop over and over again, VRP pushes the upper bound
up to TYPE_MAX (in vrp_visit_phi_node).  That TYPE_MAX does not
represent saturation; it represents overflow.  If VRP then subtracts
one from that value, it has completely lost the fact that the number
represents an overflow.

> I also do not quite understand what gains do you expect from this
> change.  You cannot reasonably expect to get anything useful for issuing
> warnings, as a large part of the ranges vrp uses are half-ranges (obtained
> from checks like a > 0), and almost any operation on half-ranges will
> create such infinities.

No.  If you look at my patch, you will see that I represent a
half-range as [0, TYPE_MAX].  I represent an overflow using a special
tree node (actually just a copy of TYPE_MAX).  So my patch correctly
distinguishes half-ranges from ranges which have overflowed.


To backtrack for a minute, the reason I am doing this is so that VRP
can issue a warning when it optimizes code like

  for (j = 1; 0 < j; j *= 2)
    if (! bigtime_test (j))
      return 1;

Here VRP currently sets j to TYPE_MAX during the loop, producing a [0,
TYPE_MAX] range, and using that to eliminate the test.  With my patch,
VRP will generate a [0, INF] range, and can issue a warning when using
that range to eliminate the test.  On the other hand, in code like
this:

  if (j > 0)
    if (j > 0)
      return 1;

VRP can use a non-overflow half-range to eliminate the second test
without a warning.

Ian