This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: lightweight class to wide int ranges in VRP and friends

On 08/24/2018 06:32 AM, Richard Biener wrote:
On Wed, Aug 15, 2018 at 7:31 PM Aldy Hernandez <> 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);
           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);
        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 ();
        bool success;
        if (code == RSHIFT_EXPR)
         success = wi_range_multiplicative_op (res, code, w0, w1);
         success = wi_range_lshift (res, w0, w1);

        if (success)
         vr->set_and_canonicalize (res, expr_type);
         vr->set_varying ();

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.


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?


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.  */
+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

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]