| Message ID | CAGm3qMXQ_-WbPNWVtyUN93MC=MVpFNHodOdUOi6CCx+CH3MuuA@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | PING: Fwd: [PATCH] Rewrite get_size_range for irange API. | expand |
PING * 2 On 8/11/20 1:56 PM, Aldy Hernandez wrote: > > ---------- Forwarded message --------- > From: *Aldy Hernandez* <aldyh@redhat.com <mailto:aldyh@redhat.com>> > Date: Thu, Aug 6, 2020, 16:54 > Subject: [PATCH] Rewrite get_size_range for irange API. > To: <gcc-patches@gcc.gnu.org <mailto:gcc-patches@gcc.gnu.org>> > Cc: <msebor@redhat.com <mailto:msebor@redhat.com>>, Aldy Hernandez > <aldyh@redhat.com <mailto:aldyh@redhat.com>> > > > [Martin, does this sound reasonable to you?] > > The following patch converts get_size_range to the irange API, thus > removing the use of VR_ANTI_RANGE. > > This was a bit tricky because of the gymnastics we do in get_size_range > to ignore negatives and all that. I didn't convert the function for > multi-ranges. The code still returns a pair of trees indicating the > massaged range. But I do believe the code is cleaner and smaller. > > I'm not sure the current code (or my adaptation) gets all cases, but > the goal was to keep to the existing functionality, nothing more. > > OK? > > gcc/ChangeLog: > > * calls.c (range_remove_non_positives): New. > (set_bounds_from_range): New. > (get_size_range): Rewrite for irange API. > * tree-affine.c (expr_to_aff_combination): Call > determine_value_range > with a range. > * tree-vrp.c (determine_value_range_1): Rename to... > (determine_value_range): ...this. > * tree-vrp.h (determine_value_range): Adjust prototype. > --- > gcc/calls.c | 139 ++++++++++++++++++---------------------------- > gcc/tree-affine.c | 5 +- > gcc/tree-vrp.c | 44 ++++++--------- > gcc/tree-vrp.h | 2 +- > 4 files changed, 73 insertions(+), 117 deletions(-) > > diff --git a/gcc/calls.c b/gcc/calls.c > index 44401e6350d..4aeeb36a2be 100644 > --- a/gcc/calls.c > +++ b/gcc/calls.c > @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see > #include "attribs.h" > #include "builtins.h" > #include "gimple-fold.h" > +#include "range.h" > > /* Like PREFERRED_STACK_BOUNDARY but in units of bytes, not bits. */ > #define STACK_BYTES (PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT) > @@ -1237,6 +1238,31 @@ alloc_max_size (void) > return alloc_object_size_limit; > } > > +// Remove non-positive numbers from a range. ALLOW_ZERO is TRUE if 0 > +// is considered positive. > + > +static void > +range_remove_non_positives (irange *vr, bool allow_zero) > +{ > + tree floor, type = vr->type (); > + if (allow_zero) > + floor = build_zero_cst (type); > + else > + floor = build_one_cst (type); > + value_range positives (floor, TYPE_MAX_VALUE (type)); > + vr->intersect (positives); > +} > + > +// Set the extreme bounds of range VR into range[]. > + > +static bool > +set_bounds_from_range (const irange *vr, tree range[2]) > +{ > + range[0] = wide_int_to_tree (vr->type (), vr->lower_bound ()); > + range[1] = wide_int_to_tree (vr->type (), vr->upper_bound ()); > + return true; > +} > + > /* Return true when EXP's range can be determined and set RANGE[] to it > after adjusting it if necessary to make EXP a represents a valid size > of object, or a valid size argument to an allocation function declared > @@ -1250,9 +1276,11 @@ alloc_max_size (void) > bool > get_size_range (tree exp, tree range[2], bool allow_zero /* = false */) > { > - if (!exp) > - return false; > - > + if (!exp || !INTEGRAL_TYPE_P (TREE_TYPE (exp))) > + { > + range[0] = range[1] = NULL_TREE; > + return false; > + } > if (tree_fits_uhwi_p (exp)) > { > /* EXP is a constant. */ > @@ -1261,91 +1289,30 @@ get_size_range (tree exp, tree range[2], bool > allow_zero /* = false */) > } > > tree exptype = TREE_TYPE (exp); > - bool integral = INTEGRAL_TYPE_P (exptype); > - > - wide_int min, max; > - enum value_range_kind range_type; > - > - if (integral) > - range_type = determine_value_range (exp, &min, &max); > - else > - range_type = VR_VARYING; > - > - if (range_type == VR_VARYING) > + value_range vr; > + determine_value_range (&vr, exp); > + if (vr.num_pairs () == 1) > + return set_bounds_from_range (&vr, range); > + > + widest_irange positives (vr); > + range_remove_non_positives (&positives, allow_zero); > + > + // If all numbers are negative, let the caller sort it out. > + if (positives.undefined_p ()) > + return set_bounds_from_range (&vr, range); > + > + // Remove the unknown parts of a multi-range. > + // This will transform [5,10][20,MAX] into [5,10]. > + int pairs = positives.num_pairs (); > + if (pairs > 1 > + && positives.upper_bound () == wi::to_wide (TYPE_MAX_VALUE > (exptype))) > { > - if (integral) > - { > - /* Use the full range of the type of the expression when > - no value range information is available. */ > - range[0] = TYPE_MIN_VALUE (exptype); > - range[1] = TYPE_MAX_VALUE (exptype); > - return true; > - } > - > - range[0] = NULL_TREE; > - range[1] = NULL_TREE; > - return false; > + value_range last_range (exptype, > + positives.lower_bound (pairs - 1), > + positives.upper_bound (pairs - 1), > VR_ANTI_RANGE); > + positives.intersect (last_range); > } > - > - unsigned expprec = TYPE_PRECISION (exptype); > - > - bool signed_p = !TYPE_UNSIGNED (exptype); > - > - if (range_type == VR_ANTI_RANGE) > - { > - if (signed_p) > - { > - if (wi::les_p (max, 0)) > - { > - /* EXP is not in a strictly negative range. That means > - it must be in some (not necessarily strictly) positive > - range which includes zero. Since in signed to unsigned > - conversions negative values end up converted to large > - positive values, and otherwise they are not valid sizes, > - the resulting range is in both cases [0, TYPE_MAX]. */ > - min = wi::zero (expprec); > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - else if (wi::les_p (min - 1, 0)) > - { > - /* EXP is not in a negative-positive range. That means EXP > - is either negative, or greater than max. Since negative > - sizes are invalid make the range [MAX + 1, TYPE_MAX]. */ > - min = max + 1; > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - else > - { > - max = min - 1; > - min = wi::zero (expprec); > - } > - } > - else if (wi::eq_p (0, min - 1)) > - { > - /* EXP is unsigned and not in the range [1, MAX]. That means > - it's either zero or greater than MAX. Even though 0 would > - normally be detected by -Walloc-zero, unless ALLOW_ZERO > - is true, set the range to [MAX, TYPE_MAX] so that when MAX > - is greater than the limit the whole range is diagnosed. */ > - if (allow_zero) > - min = max = wi::zero (expprec); > - else > - { > - min = max + 1; > - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); > - } > - } > - else > - { > - max = min - 1; > - min = wi::zero (expprec); > - } > - } > - > - range[0] = wide_int_to_tree (exptype, min); > - range[1] = wide_int_to_tree (exptype, max); > - > - return true; > + return set_bounds_from_range (&positives, range); > } > > /* Diagnose a call EXP to function FN decorated with attribute alloc_size > diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c > index 5620e6bf28f..2a1b1872e27 100644 > --- a/gcc/tree-affine.c > +++ b/gcc/tree-affine.c > @@ -340,7 +340,7 @@ expr_to_aff_combination (aff_tree *comb, tree_code > code, tree type, > op1 = fold_convert (otype, op1); > return expr_to_aff_combination (comb, icode, otype, > op0, op1); > } > - wide_int minv, maxv; > + value_range vr; > /* If inner type has wrapping overflow behavior, fold > conversion > for below case: > (T1)(X *+- CST) -> (T1)X *+- (T1)CST > @@ -348,10 +348,11 @@ expr_to_aff_combination (aff_tree *comb, tree_code > code, tree type, > if (TYPE_UNSIGNED (itype) > && TYPE_OVERFLOW_WRAPS (itype) > && TREE_CODE (op1) == INTEGER_CST > - && determine_value_range (op0, &minv, &maxv) == VR_RANGE) > + && determine_value_range (&vr, op0)) > { > wi::overflow_type overflow = wi::OVF_NONE; > signop sign = UNSIGNED; > + wide_int minv = vr.lower_bound (), maxv = vr.upper_bound (); > if (icode == PLUS_EXPR) > wi::add (maxv, wi::to_wide (op1), sign, &overflow); > else if (icode == MULT_EXPR) > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index de84c1d505d..2078cd246c6 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -4565,25 +4565,30 @@ make_pass_vrp (gcc::context *ctxt) > } > > > -/* Worker for determine_value_range. */ > +/* Compute a value-range for EXPR and set it in *VR. Return TRUE if range > + found was neither varying nor undefined. */ > > -static void > -determine_value_range_1 (value_range *vr, tree expr) > +bool > +determine_value_range (irange *vr, tree expr) > { > if (BINARY_CLASS_P (expr)) > { > - value_range vr0, vr1; > - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); > - determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1)); > - range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), > + value_range res, vr0, vr1; > + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); > + determine_value_range (&vr1, TREE_OPERAND (expr, 1)); > + range_fold_binary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), > &vr0, &vr1); > + res.normalize_symbolics (); > + *vr = res; > } > else if (UNARY_CLASS_P (expr)) > { > - value_range vr0; > - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); > - range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), > + value_range res, vr0; > + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); > + range_fold_unary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), > &vr0, TREE_TYPE (TREE_OPERAND (expr, 0))); > + res.normalize_symbolics (); > + *vr = res; > } > else if (TREE_CODE (expr) == INTEGER_CST) > vr->set (expr); > @@ -4602,22 +4607,5 @@ determine_value_range_1 (value_range *vr, tree expr) > else > vr->set_varying (TREE_TYPE (expr)); > } > -} > - > -/* Compute a value-range for EXPR and set it in *MIN and *MAX. Return > - the determined range type. */ > - > -value_range_kind > -determine_value_range (tree expr, wide_int *min, wide_int *max) > -{ > - value_range vr; > - determine_value_range_1 (&vr, expr); > - if (vr.constant_p ()) > - { > - *min = wi::to_wide (vr.min ()); > - *max = wi::to_wide (vr.max ()); > - return vr.kind (); > - } > - > - return VR_VARYING; > + return !vr->varying_p () && !vr->undefined_p (); > } > diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h > index 371e58aa0ea..54c88c93d48 100644 > --- a/gcc/tree-vrp.h > +++ b/gcc/tree-vrp.h > @@ -61,7 +61,7 @@ extern bool find_case_label_index (gswitch *, size_t, > tree, size_t *); > extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); > extern tree get_single_symbol (tree, bool *, tree *); > extern void maybe_set_nonzero_bits (edge, tree); > -extern value_range_kind determine_value_range (tree, wide_int *, > wide_int *); > +extern bool determine_value_range (irange *vr, tree); > extern wide_int masked_increment (const wide_int &val_in, const > wide_int &mask, > const wide_int &sgnbit, unsigned int > prec); > > -- > 2.26.2 >
diff --git a/gcc/calls.c b/gcc/calls.c index 44401e6350d..4aeeb36a2be 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "builtins.h" #include "gimple-fold.h" +#include "range.h" /* Like PREFERRED_STACK_BOUNDARY but in units of bytes, not bits. */ #define STACK_BYTES (PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT) @@ -1237,6 +1238,31 @@ alloc_max_size (void) return alloc_object_size_limit; } +// Remove non-positive numbers from a range. ALLOW_ZERO is TRUE if 0 +// is considered positive. + +static void +range_remove_non_positives (irange *vr, bool allow_zero) +{ + tree floor, type = vr->type (); + if (allow_zero) + floor = build_zero_cst (type); + else + floor = build_one_cst (type); + value_range positives (floor, TYPE_MAX_VALUE (type)); + vr->intersect (positives); +} + +// Set the extreme bounds of range VR into range[]. + +static bool +set_bounds_from_range (const irange *vr, tree range[2]) +{ + range[0] = wide_int_to_tree (vr->type (), vr->lower_bound ()); + range[1] = wide_int_to_tree (vr->type (), vr->upper_bound ()); + return true; +} + /* Return true when EXP's range can be determined and set RANGE[] to it after adjusting it if necessary to make EXP a represents a valid size of object, or a valid size argument to an allocation function declared @@ -1250,9 +1276,11 @@ alloc_max_size (void) bool get_size_range (tree exp, tree range[2], bool allow_zero /* = false */) { - if (!exp) - return false; - + if (!exp || !INTEGRAL_TYPE_P (TREE_TYPE (exp))) + { + range[0] = range[1] = NULL_TREE; + return false; + } if (tree_fits_uhwi_p (exp)) { /* EXP is a constant. */ @@ -1261,91 +1289,30 @@ get_size_range (tree exp, tree range[2], bool allow_zero /* = false */) } tree exptype = TREE_TYPE (exp); - bool integral = INTEGRAL_TYPE_P (exptype); - - wide_int min, max; - enum value_range_kind range_type; - - if (integral) - range_type = determine_value_range (exp, &min, &max); - else - range_type = VR_VARYING; - - if (range_type == VR_VARYING) + value_range vr; + determine_value_range (&vr, exp); + if (vr.num_pairs () == 1) + return set_bounds_from_range (&vr, range); + + widest_irange positives (vr); + range_remove_non_positives (&positives, allow_zero); + + // If all numbers are negative, let the caller sort it out. + if (positives.undefined_p ()) + return set_bounds_from_range (&vr, range); + + // Remove the unknown parts of a multi-range. + // This will transform [5,10][20,MAX] into [5,10]. + int pairs = positives.num_pairs (); + if (pairs > 1 + && positives.upper_bound () == wi::to_wide (TYPE_MAX_VALUE (exptype))) { - if (integral) - { - /* Use the full range of the type of the expression when - no value range information is available. */ - range[0] = TYPE_MIN_VALUE (exptype); - range[1] = TYPE_MAX_VALUE (exptype); - return true; - } - - range[0] = NULL_TREE; - range[1] = NULL_TREE; - return false; + value_range last_range (exptype, + positives.lower_bound (pairs - 1), + positives.upper_bound (pairs - 1), VR_ANTI_RANGE); + positives.intersect (last_range); } - - unsigned expprec = TYPE_PRECISION (exptype); - - bool signed_p = !TYPE_UNSIGNED (exptype); - - if (range_type == VR_ANTI_RANGE) - { - if (signed_p) - { - if (wi::les_p (max, 0)) - { - /* EXP is not in a strictly negative range. That means - it must be in some (not necessarily strictly) positive - range which includes zero. Since in signed to unsigned - conversions negative values end up converted to large - positive values, and otherwise they are not valid sizes, - the resulting range is in both cases [0, TYPE_MAX]. */ - min = wi::zero (expprec); - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); - } - else if (wi::les_p (min - 1, 0)) - { - /* EXP is not in a negative-positive range. That means EXP - is either negative, or greater than max. Since negative - sizes are invalid make the range [MAX + 1, TYPE_MAX]. */ - min = max + 1; - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); - } - else - { - max = min - 1; - min = wi::zero (expprec); - } - } - else if (wi::eq_p (0, min - 1)) - { - /* EXP is unsigned and not in the range [1, MAX]. That means - it's either zero or greater than MAX. Even though 0 would - normally be detected by -Walloc-zero, unless ALLOW_ZERO - is true, set the range to [MAX, TYPE_MAX] so that when MAX - is greater than the limit the whole range is diagnosed. */ - if (allow_zero) - min = max = wi::zero (expprec); - else - { - min = max + 1; - max = wi::to_wide (TYPE_MAX_VALUE (exptype)); - } - } - else - { - max = min - 1; - min = wi::zero (expprec); - } - } - - range[0] = wide_int_to_tree (exptype, min); - range[1] = wide_int_to_tree (exptype, max); - - return true; + return set_bounds_from_range (&positives, range); } /* Diagnose a call EXP to function FN decorated with attribute alloc_size diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index 5620e6bf28f..2a1b1872e27 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -340,7 +340,7 @@ expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, op1 = fold_convert (otype, op1); return expr_to_aff_combination (comb, icode, otype, op0, op1); } - wide_int minv, maxv; + value_range vr; /* If inner type has wrapping overflow behavior, fold conversion for below case: (T1)(X *+- CST) -> (T1)X *+- (T1)CST @@ -348,10 +348,11 @@ expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, if (TYPE_UNSIGNED (itype) && TYPE_OVERFLOW_WRAPS (itype) && TREE_CODE (op1) == INTEGER_CST - && determine_value_range (op0, &minv, &maxv) == VR_RANGE) + && determine_value_range (&vr, op0)) { wi::overflow_type overflow = wi::OVF_NONE; signop sign = UNSIGNED; + wide_int minv = vr.lower_bound (), maxv = vr.upper_bound (); if (icode == PLUS_EXPR) wi::add (maxv, wi::to_wide (op1), sign, &overflow); else if (icode == MULT_EXPR) diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index de84c1d505d..2078cd246c6 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4565,25 +4565,30 @@ make_pass_vrp (gcc::context *ctxt) } -/* Worker for determine_value_range. */ +/* Compute a value-range for EXPR and set it in *VR. Return TRUE if range + found was neither varying nor undefined. */ -static void -determine_value_range_1 (value_range *vr, tree expr) +bool +determine_value_range (irange *vr, tree expr) { if (BINARY_CLASS_P (expr)) { - value_range vr0, vr1; - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); - determine_value_range_1 (&vr1, TREE_OPERAND (expr, 1)); - range_fold_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), + value_range res, vr0, vr1; + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); + determine_value_range (&vr1, TREE_OPERAND (expr, 1)); + range_fold_binary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), &vr0, &vr1); + res.normalize_symbolics (); + *vr = res; } else if (UNARY_CLASS_P (expr)) { - value_range vr0; - determine_value_range_1 (&vr0, TREE_OPERAND (expr, 0)); - range_fold_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr), + value_range res, vr0; + determine_value_range (&vr0, TREE_OPERAND (expr, 0)); + range_fold_unary_expr (&res, TREE_CODE (expr), TREE_TYPE (expr), &vr0, TREE_TYPE (TREE_OPERAND (expr, 0))); + res.normalize_symbolics (); + *vr = res; } else if (TREE_CODE (expr) == INTEGER_CST) vr->set (expr); @@ -4602,22 +4607,5 @@ determine_value_range_1 (value_range *vr, tree expr) else vr->set_varying (TREE_TYPE (expr)); } -} - -/* Compute a value-range for EXPR and set it in *MIN and *MAX. Return - the determined range type. */ - -value_range_kind -determine_value_range (tree expr, wide_int *min, wide_int *max) -{ - value_range vr; - determine_value_range_1 (&vr, expr); - if (vr.constant_p ()) - { - *min = wi::to_wide (vr.min ()); - *max = wi::to_wide (vr.max ()); - return vr.kind (); - } - - return VR_VARYING; + return !vr->varying_p () && !vr->undefined_p (); } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 371e58aa0ea..54c88c93d48 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -61,7 +61,7 @@ extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); extern tree get_single_symbol (tree, bool *, tree *); extern void maybe_set_nonzero_bits (edge, tree); -extern value_range_kind determine_value_range (tree, wide_int *, wide_int *); +extern bool determine_value_range (irange *vr, tree); extern wide_int masked_increment (const wide_int &val_in, const wide_int
---------- Forwarded message --------- From: Aldy Hernandez <aldyh@redhat.com> Date: Thu, Aug 6, 2020, 16:54 Subject: [PATCH] Rewrite get_size_range for irange API. To: <gcc-patches@gcc.gnu.org> Cc: <msebor@redhat.com>, Aldy Hernandez <aldyh@redhat.com> [Martin, does this sound reasonable to you?] The following patch converts get_size_range to the irange API, thus removing the use of VR_ANTI_RANGE. This was a bit tricky because of the gymnastics we do in get_size_range to ignore negatives and all that. I didn't convert the function for multi-ranges. The code still returns a pair of trees indicating the massaged range. But I do believe the code is cleaner and smaller. I'm not sure the current code (or my adaptation) gets all cases, but the goal was to keep to the existing functionality, nothing more. OK? gcc/ChangeLog: * calls.c (range_remove_non_positives): New. (set_bounds_from_range): New. (get_size_range): Rewrite for irange API. * tree-affine.c (expr_to_aff_combination): Call determine_value_range with a range. * tree-vrp.c (determine_value_range_1): Rename to... (determine_value_range): ...this. * tree-vrp.h (determine_value_range): Adjust prototype. --- gcc/calls.c | 139 ++++++++++++++++++---------------------------- gcc/tree-affine.c | 5 +- gcc/tree-vrp.c | 44 ++++++--------- gcc/tree-vrp.h | 2 +- 4 files changed, 73 insertions(+), 117 deletions(-) &mask, const wide_int &sgnbit, unsigned int prec);