Add overflow infinity handling to VRP

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Wed Jan 3 20:12:00 GMT 2007


Hello,

> > > 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.

well, it represents saturation in the same sense arithmetic does;
if we have loop for (i = 0; ; i++) and addition in the type of i
is (considered to be) saturating, then the range of i is [0,MAX].
Sorry, I still fail to see the difference.

> 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.

So what will [0, TYPE_MAX] + 1 return?  Will it return
[1, INFINITY] (in which case you ask for many false positives),
or [1, TYPE_MAX] (in which case the special handling of induction
variables you describe below looks just inconsistent)?

Zdenek

> 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.



More information about the Gcc-patches mailing list