On Mon, Sep 3, 2018 at 8:58 AM Aldy Hernandez <al...@redhat.com> wrote:
>
>
Can you re-base and re-post please?
Sorry for being late here.
Richard.
>
> -------- Forwarded Message --------
> Subject: Re: lightweight class to wide int ranges in VRP and friends
> Date: Fri, 24 Aug 2018 13:40:29 -0400
> From: Aldy Hernandez <al...@redhat.com>
> To: Richard Biener <richard.guent...@gmail.com>
> CC: GCC Patches <gcc-patches@gcc.gnu.org>
>
> On 08/24/2018 06:32 AM, Richard Biener wrote:
> > On Wed, Aug 15, 2018 at 7:31 PM Aldy Hernandez <al...@redhat.com> wrote:
> >>
> >> I kept seeing the same patterns over and over in all this re-factoring:
> >>
> >> 1. extract value_range constants into pairs of wide ints
> >>
> >> 2. mimic symbolics as [-MIN, +MAX] (most of the time :))
> >>
> >> 3. perform some wide int operation on the wide int range
> >>
> >> 4. convert back to a value range
> >>
> >> So I've decided to clean this up even more. Instead of passing a pair
> >> of wide ints plus sign, precision, and god knows what to every
> >> wide_int_range_* function, I've implemented a lighweight class
> >> (wi_range) for a pair of wide ints. It is not meant for long term
> >> storage, but even so its footprint is minimal.
> >>
> >> The only extra bits are another 64-bit word per pair for keeping
> >> attributes such as precision, sign, overflow_wraps, and a few other
> >> things we'll need shortly. In reality we only need one set of
> >> attributes for both sets of pairs, so we waste one 64-bit word. I don't
> >> care. They're short lived, and the resulting code looks an awful lot
> >> nicer. For example, the shift code gets rewritten from this:
> >>
> >> if (range_int_cst_p (&vr1)
> >> && !vrp_shift_undefined_p (vr1, prec))
> >> {
> >> if (code == RSHIFT_EXPR)
> >> {
> >> if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
> >> {
> >> vr0.type = type = VR_RANGE;
> >> vr0.min = vrp_val_min (expr_type);
> >> vr0.max = vrp_val_max (expr_type);
> >> }
> >> extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
> >> return;
> >> }
> >> else if (code == LSHIFT_EXPR
> >> && range_int_cst_p (&vr0))
> >> {
> >> wide_int res_lb, res_ub;
> >> if (wide_int_range_lshift (res_lb, res_ub, sign, prec,
> >> wi::to_wide (vr0.min),
> >> wi::to_wide (vr0.max),
> >> wi::to_wide (vr1.min),
> >> wi::to_wide (vr1.max),
> >> TYPE_OVERFLOW_UNDEFINED
> >> (expr_type),
> >> TYPE_OVERFLOW_WRAPS (expr_type)))
> >> {
> >> min = wide_int_to_tree (expr_type, res_lb);
> >> max = wide_int_to_tree (expr_type, res_ub);
> >> set_and_canonicalize_value_range (vr, VR_RANGE,
> >> min, max, NULL);
> >> return;
> >> }
> >> }
> >> }
> >> set_value_range_to_varying (vr);
> >>
> >> into this:
> >>
> >> wi_range w0 (&vr0, expr_type);
> >> wi_range w1 (&vr1, expr_type);
> >> if (!range_int_cst_p (&vr1)
> >> || wi_range_shift_undefined_p (w1)
> >> || (code == LSHIFT_EXPR
> >> && !range_int_cst_p (&vr0)))
> >> {
> >> vr->set_varying ();
> >> return;
> >> }
> >> bool success;
> >> if (code == RSHIFT_EXPR)
> >> success = wi_range_multiplicative_op (res, code, w0, w1);
> >> else
> >> success = wi_range_lshift (res, w0, w1);
> >>
> >> if (success)
> >> vr->set_and_canonicalize (res, expr_type);
> >> else
> >> vr->set_varying ();
> >> return;
> >
> > not sure whether I like the munging of lshift and right shift (what exactly
> > gets
> > done is less clear in your version ...). Having a light-weigth class for
> > the wi_range_ parameters is nice though.
>
> No worries. I'm not emotionally attached to munging them :).
>
> >
> >> I also munged together the maybe/mustbe nonzero_bits into one structure.
> >>
> >> Finally, I've pontificated that wide_int_range_blah is too much typing.
> >> Everyone's RSI will thank me for rewriting the methods as wi_range_blah.
> >>
> >> I've tried to keep the functionality changes to a minimum. However,
> >> there are some slight changes where I treat symbolics and VR_VARYING as
> >> [MIN, MAX] and let the constant code do its thing. It is considerably
> >> easier to read.
> >>
> >> I am finally happy with the overall direction of this. If this and the
> >> last one are acceptable, I think I only need to clean MIN/MAX_EXPR and
> >> ABS_EXPR and I'm basically done with what I need going forward.
> >>
> >> Phew...
> >>
> >> How does this look?
> >
> > +struct wi_range
> > +{
> > + wide_int min;
> > + wide_int max;
> > + /* This structure takes one additional 64-bit word apart from the
> > + min/max bounds above. It is laid out so that PRECISION and SIGN
> > + can be accessed without any bit twiddling, since they're the most
> > + commonly accessed fields. */
> > + unsigned short precision;
> > + bool empty_p:1;
> > + bool pointer_type_p:1;
> > + bool overflow_wraps:1;
> > + bool overflow_undefined:1;
> > + signop sign;
> >
> > isn't precision already available in min.get_precision () which is
> > required to be equal to max.get_precision ()?
>
> Indeed. Good point.
>
> >
> > + wi_range () { empty_p = false; }
> >
> > true I suppose? Better not allow default construction?
>
> OK.
>
> >
> > empty_p doesn't seem to be documented, nor is pointer_type_p
> > or why that is necessary - maybe simply store a tree type
> > instead all of the bits?
>
> I was trying to avoid dereferencing another pointer by perhaps
> flattening out the needed bits, but again-- not emotionally attached.
> Easier for me...
>
> >
> > +/* A structure to pass maybe and mustbe nonzero bitmasks. This is for
> > + use in wi_range_set_zero_nonzero_bits and friends. */
> > +
> > +struct maybe_nonzero_bits
> > +{
> > + /* If some bit is unset, it means that for all numbers in the range
> > + the bit is 0, otherwise it might be 0 or 1. */
> > + wide_int may_be;
> > +
> > + /* If some bit is set, it means that for all numbers in the range
> > + the bit is 1, otherwise it might be 0 or 1. */
> > + wide_int must_be;
> > };
> >
> > eh - multiple changes in one patch ...
>
> Well, is it? I'm trying to avoid passing tons of things to the
> wide_int_range_* functions, and that includes wide ints and the nonzero
> bit pairs. Could I please leave these in the patch?
>
> >
> > @@ -52,6 +54,58 @@ struct GTY((for_user)) value_range
> >
> > /* Dump value range to stderr. */
> > void dump ();
> > +
> > + void set (const wi_range &r, tree type);
> > + void set_and_canonicalize (const wi_range &r, tree type);
> > + void set_undefined ();
> > + void set_varying ();
> > +};
> >
> > likewise ... you introduce those methods but not use them consistently.
> > Please leave out this change (I would object to this kind of change
> > if carried out through).
>
> I was really avoiding having to convert every caller. But really, why
> would you object even if carried out through?
>
> >
> > +/* Construct a new range from the contents of a value_range. Varying
> > + or symbolic ranges are normalized to the entire possible range. */
> > +
> > +inline
> > +wi_range::wi_range (value_range *vr, tree type)
> > +{
> > + precision = TYPE_PRECISION (type);
> > + pointer_type_p = POINTER_TYPE_P (type);
> > + overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
> > + overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
> > + sign = TYPE_SIGN (type);
> > + empty_p = false;
> > + if (vr->type == VR_VARYING || symbolic_range_p (vr))
> > + {
> > + min = wi::min_value (precision, sign);
> > + max = wi::max_value (precision, sign);
> > + }
> > + else if (vr->type == VR_RANGE)
> > + {
> > + min = wi::to_wide (vr->min);
> > + max = wi::to_wide (vr->max);
> > + }
> > + else
> > + gcc_unreachable ();
> > +}
> >
> > What about VR_ANTI_RANGE? Note the above doesn't exactly look
> > "light-weight".
>
> Yes, I should handle anti range, or ICE or something, considering the
> pain it was to find the anti range problem with the POINTER_PLUS_EXPR
> code recently.
>
> Is "not exactly light-weight" an objection, or just a btw type of
> comment :)? Would it make it less painful if we stored the entire type
> in the wi_range as mentioned earlier?
>
> >
> > -/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
> > - [WMIN,WMAX]. */
> > +/* Calculate TRUNC_MOD_EXPR on two ranges and store the result in RES.
> > + Return TRUE if operation succeeded. */
> >
> > did I say multiple changes...? I think this isn't a good one given
> > "succeed"
> > doesn't imply that if not the result is UNDEFINED ...
>
> Point taken, but hey I can't read your responses as you're typing them ;-).
>
> >
> > As said above the shift handlign structrue is now unreadable :/ Given we do
> > different things for lshift vs. rshift it makes sense to simply split
>
> Unreadable? Surely you jest! As opposed to the super-readable stuff in
> VRP before? Come on! But I can split the shifts. That's not a problem :).
>
> >
> > else if (code == RSHIFT_EXPR
> > || code == LSHIFT_EXPR)
> > {
> >
> > even if that means duplicating a few lines.
> >
> > Just to remind you review (and approval) isn't easier if you put unrelated
> > stuff
> > into a patch ;)
>
> If you mention it three times in a review and I apologize three times,
> are we at peace now? :-P
>
> Aldy
