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