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

[Richard Biener]

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.

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

Thanks,
Richard.

> Aldy
>
> >
> >>
> >> It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without
> >> bailing as VR_VARYING in extract_range_from_binary_expr_1.  In doing so,
> >> I also noticed that ~[0,0] is not the only non-null.  We could also have
> >> ~[0,2] and still know that the pointer is not zero.  I have adjusted
> >> range_is_nonnull accordingly.
> >
> > But there are other consumers and it would have been better to
> > change range_includes_zero_p to do the natural thing (get a VR) and
> > then remove range_is_nonnull as redundant if possible.
> >
> >>
> >> (Yes, we can get something like ~[0,2] for a pointer for things like the
> >> following in libgcc:
> >>
> >>     if (segment_arg == (void *) (uintptr_type) 1)
> >>       ...
> >>     else if (segment_arg == (void *) (uintptr_type) 2)
> >>       return NULL;
> >>     else if (segment_arg != NULL)
> >>       segment = (struct stack_segment *) segment_arg;
> >> )
> >>
> >> BTW, I am still not happy with the entire interface to wide-int-range.*,
> >> and have another pending patchset that will simplify things even
> >> further.  I think everyone will be pleased ;-).
> >>
> >> OK pending another round of tests?
> >
> > The division related changes are OK, please split out & improve the nonnull
> > parts (and the POINTER_PLUS_EXPR check is already in as variant).
> >
> > Richard.
> >
> >>
> >> Aldy