Re: VRP: rewrite the division code (to handle corner cases including 0)

[Aldy Hernandez <aldyh at redhat dot com>]

On 08/23/2018 08:51 AM, Richard Biener wrote:
> On Tue, Aug 21, 2018 at 7:35 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> > On 08/21/2018 05:46 AM, Richard Biener wrote:
> > > On Wed, Aug 15, 2018 at 3:33 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> > > > Howdy!
> > > >
> > > > In auditing the *_DIV_EXPR code I noticed that we were really botching
> > > > some divisions where the divisor included 0.
> > > >
> > > > Particularly interesting was that we were botching something as simple
> > > > as dividing by [0,0].  We were also incorrectly calculating things like
> > > > [-2,-2] / [0, 5555], where we should have removed the 0 from the divisor.
> > > >
> > > > Also, the symbolic special casing could be handled by just treating
> > > > symbolic ranges as [-MIN, +MAX] and letting the common code handle then.
> > > >     Similarly for anti ranges, which actually never happen except for the
> > > > constant case, since they've been normalized earlier.
> > >
> > > Note we also have "mixed" symbolic (anti-)ranges like [0, a].  I don't think
> > > we handled those before but extract_range_to_wide_ints may be improved
> > > to handle them.  Likewise ranges_from_anti_range, ~[0, a] -> [-INF,
> > > -1] u [a+1, +INF]
> > > though not sure if that helps any case in practice.
> >
> > I have added comments for a future improvements.  Perhaps after the dust
> > settles...
>
> Good ;)
>
> > > > All in all, it was much easier to normalize all the symbolic ranges and
> > > > treat everything generically by performing the division in two chunks...
> > > > the negative numbers and the (non-zero) positive numbers.  And finally,
> > > > unioning the results.  This makes everything much simpler to read with
> > > > minimal special casing.
> > >
> > > Yeah, nice work.  Few comments:
> > >
> > > +                              TYPE_OVERFLOW_UNDEFINED (expr_type),
> > > +                              TYPE_OVERFLOW_WRAPS (expr_type),
> > >
> > > we no longer have the third state !UNDEFINED && !WRAPS so I suggest
> > > to eliminate one for the other (just pass TYPE_OVERFLOW_UNDEFINED).
> >
> > I'm confused.  Then what shall I pass to
> > wide_int_range_multiplicative_op within wide_int_range_div?  Are you
> > expecting to pass overflow_undefined to both the overflow_undefined and
> > overflow_wraps arguments in multiplicative_op?  Or are you saying I
> > should get rid of overflow_wraps in both wide_int_range_div and
> > wide_int_range_multiplicative_op (plus all other users of
> > w_i_r_multiplicative_op)?
>
> Yes, overflow_wraps == !overflow_undefined (well, OK, not exactly - there's
> also TYPE_OVERFLOW_TRAPS, but not for pointers).
>
> Let's sort this out as a followup.  It somewhat felt odd / inconsistent.

Ok, I'm drowning myself in changes here.  I've put this on my short-term 
todo list, and will revisit once the dust settles-- hopefully in a week.

> I think the wide-int routines want to know whether the operation may
> overflow or not and if it may then it simply assumes wrapping behavior.
> When overflow is undefined or if it traps the overflow isn't observed
> in the result ...
>
> > > +  /* If we're definitely dividing by zero, there's nothing to do.  */
> > > +  if (wide_int_range_zero_p (divisor_min, divisor_max, prec))
> > > +    return false;
> > >
> > > I know we didn't do this before but for x / 0 we should compute UNDEFINED
> > > as range.  With the current interfacing this special case would require handling
> > > in the non-wide-int caller.
> >
> > I've added the following, since I'm unsure whether we should return
> > undefined or varying for non_call_exceptions.  What do you think?
> >
> >         /* Special case explicit division by zero as undefined.  */
> >         if (range_is_null (&vr1))
> >          {
> >            /* However, we must not eliminate a division by zero if
> >               flag_non_call_exceptions.  */
> >            if (cfun->can_throw_non_call_exceptions)
> >              set_value_range_to_varying (vr);
> >            else
> >              set_value_range_to_undefined (vr);
> >            return;
> >          }
>
> ... which means even for non-call-exceptions the actual _result_ of
> a division by zero is UNDEFINED.  When an exception is thrown
> we're just not reaching any consumer of the result.
>
> > > > Finally, my apologies for including a tiny change to the
> > > > POINTER_PLUS_EXPR handling code as well.  It came about the same set of
> > > > auditing tests.
> > >
> > > Bah, please split up things here ;)  I've done a related change there
> > > yesterday...
> >
> > Ughh... Will do.  I figured someone would complain ;-).
>
> ;)
>
> The patch is OK unchanged or with the division-by-zero changed to
> VR_UNDEFINED unconditionally (you can also do/test that as followup,
> but make sure to enable Ada for testing).

Likewise.  I've added this to my list, and will revisit shortly.

Ada?  What's that?  Is that what I test right before I merge a branch 
with tons of changes into mainline? *hides in shame*

I'm committing as is.  Thanks.
Aldy