Message ID | 803fa05d-48e3-b9e8-b65c-abfae88e0d3a@redhat.com |
---|---|
State | New |
Headers | show |
Series | abstract wide int binop code from VRP | expand |
Hmmm, I think we can do better, and since this hasn't been reviewed yet, I don't think anyone will mind the adjustment to the patch ;-). I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract them into properly named poly_int_binop, wide_int_binop, and tree_binop, and then use a default argument for int_const_binop() to get things going. Sorry for more changes in flight, but I thought we could benefit from more cleanups :). OK for trunk pending tests? Aldy On 07/10/2018 04:31 AM, Aldy Hernandez wrote: > Howdy! > > Attached are more cleanups to VRP getting rid of some repetitive code, > as well as abstracting wide int handling code into their own functions. > There should be no change to existing functionality. > > You may notice that I have removed the PLUS/MINUS_EXPR handling in > vrp_int_const_binop, even from the new abstracted code: > > - /* For addition, the operands must be of the same sign > - to yield an overflow. Its sign is therefore that > - of one of the operands, for example the first. */ > - || (code == PLUS_EXPR && sgn1 >= 0) > - /* For subtraction, operands must be of > - different signs to yield an overflow. Its sign is > - therefore that of the first operand or the opposite of > - that of the second operand. A first operand of 0 counts > - as positive here, for the corner case 0 - (-INF), which > - overflows, but must yield +INF. */ > - || (code == MINUS_EXPR && sgn1 >= 0) > > This code is actually unreachable, as the switch above this snippet was > already aborting if code was not one of the shift or mult/div operators. > > Oh yeah, don't blame me for the cryptic comment to > range_easy_mask_min_mask(). That machine language comment was already > there ;-). > > OK pending one more round of tests? > > Aldy gcc/ * fold-const.c (int_const_binop_1): Abstract... (wide_int_binop): ...wide int code here. (poly_int_binop): ...poly int code here. (tree_binop): ...tree code here. * fold-const.h (wide_int_binop): New. * tree-vrp.c (vrp_int_const_binop): Call wide_int_binop. Remove useless PLUS/MINUS_EXPR case. (zero_nonzero_bits_from_vr): Move wide int code... (zero_nonzero_bits_from_bounds): ...here. (extract_range_from_binary_expr_1): Move mask optimization code... (range_easy_mask_min_max): ...here. * tree-vrp.h (zero_nonzero_bits_from_bounds): New. (range_easy_mask_min_max): New. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 97c435fa5e0..4614b8adcf4 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -966,21 +966,17 @@ int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2 && TYPE_MODE (type1) == TYPE_MODE (type2); } -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce + a new constant in RES. Return FALSE if we don't know how to + evaluate CODE at compile-time. */ -static tree -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, - int overflowable) +bool +wide_int_binop (enum tree_code code, + wide_int &res, const wide_int &arg1, const wide_int &arg2, + signop sign, wi::overflow_type &overflow) { - wide_int res; - tree t; - tree type = TREE_TYPE (parg1); - signop sign = TYPE_SIGN (type); - wi::overflow_type overflow = wi::OVF_NONE; - - wi::tree_to_wide_ref arg1 = wi::to_wide (parg1); - wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); - + wide_int tmp; + overflow = wi::OVF_NONE; switch (code) { case BIT_IOR_EXPR: @@ -999,37 +995,41 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case LSHIFT_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RSHIFT_EXPR) code = LSHIFT_EXPR; else code = RSHIFT_EXPR; } + else + tmp = arg2; if (code == RSHIFT_EXPR) /* It's unclear from the C standard whether shifts can overflow. The following code ignores overflow; perhaps a C standard interpretation ruling is needed. */ - res = wi::rshift (arg1, arg2, sign); + res = wi::rshift (arg1, tmp, sign); else - res = wi::lshift (arg1, arg2); + res = wi::lshift (arg1, tmp); break; case RROTATE_EXPR: case LROTATE_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RROTATE_EXPR) code = LROTATE_EXPR; else code = RROTATE_EXPR; } + else + tmp = arg2; if (code == RROTATE_EXPR) - res = wi::rrotate (arg1, arg2); + res = wi::rrotate (arg1, tmp); else - res = wi::lrotate (arg1, arg2); + res = wi::lrotate (arg1, tmp); break; case PLUS_EXPR: @@ -1051,49 +1051,49 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_floor (arg1, arg2, sign, &overflow); break; case CEIL_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_ceil (arg1, arg2, sign, &overflow); break; case ROUND_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_round (arg1, arg2, sign, &overflow); break; case TRUNC_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_floor (arg1, arg2, sign, &overflow); break; case CEIL_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_ceil (arg1, arg2, sign, &overflow); break; case ROUND_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_round (arg1, arg2, sign, &overflow); break; @@ -1106,8 +1106,28 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, break; default: - return NULL_TREE; + return false; } + return true; +} + +/* Subroutine of int_const_binop that handles two INTEGER_CSTs. */ + +static tree +tree_binop (enum tree_code code, const_tree parg1, const_tree parg2, + int overflowable) +{ + wide_int res; + tree t; + tree type = TREE_TYPE (parg1); + signop sign = TYPE_SIGN (type); + wi::overflow_type overflow = wi::OVF_NONE; + + wide_int arg1 = wi::to_wide (parg1); + wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); + + if (!wide_int_binop (code, res, arg1, arg2, sign, overflow)) + return NULL_TREE; t = force_fit_type (type, res, overflowable, (((sign == SIGNED || overflowable == -1) @@ -1117,78 +1137,81 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, return t; } -/* Combine two integer constants PARG1 and PARG2 under operation CODE - to produce a new constant. Return NULL_TREE if we don't know how - to evaluate CODE at compile-time. */ +/* Subroutine of int_const_binop that handles two POLY_INTs. */ static tree -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, - int overflowable) +poly_int_binop (enum tree_code code, const_tree arg1, const_tree arg2, + int overflowable = 1) { - if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) - return int_const_binop_2 (code, arg1, arg2, overflowable); - gcc_assert (NUM_POLY_INT_COEFFS != 1); - if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + gcc_assert (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)); + + poly_wide_int res; + wi::overflow_type overflow; + tree type = TREE_TYPE (arg1); + signop sign = TYPE_SIGN (type); + switch (code) { - poly_wide_int res; - wi::overflow_type overflow; - tree type = TREE_TYPE (arg1); - signop sign = TYPE_SIGN (type); - switch (code) - { - case PLUS_EXPR: - res = wi::add (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case PLUS_EXPR: + res = wi::add (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MINUS_EXPR: - res = wi::sub (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case MINUS_EXPR: + res = wi::sub (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MULT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg1), - wi::to_wide (arg2), sign, &overflow); - else if (TREE_CODE (arg1) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg2), - wi::to_wide (arg1), sign, &overflow); - else - return NULL_TREE; - break; + case MULT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg1), + wi::to_wide (arg2), sign, &overflow); + else if (TREE_CODE (arg1) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg2), + wi::to_wide (arg1), sign, &overflow); + else + return NULL_TREE; + break; - case LSHIFT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); - else - return NULL_TREE; - break; + case LSHIFT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); + else + return NULL_TREE; + break; - case BIT_IOR_EXPR: - if (TREE_CODE (arg2) != INTEGER_CST - || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), - &res)) - return NULL_TREE; - break; + case BIT_IOR_EXPR: + if (TREE_CODE (arg2) != INTEGER_CST + || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), + &res)) + return NULL_TREE; + break; - default: - return NULL_TREE; - } - return force_fit_type (type, res, overflowable, - (((sign == SIGNED || overflowable == -1) - && overflow) - | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); + default: + return NULL_TREE; } - - return NULL_TREE; + return force_fit_type (type, res, overflowable, + (((sign == SIGNED || overflowable == -1) + && overflow) + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); } +/* Combine two integer constants PARG1 and PARG2 under operation CODE + to produce a new constant. Return NULL_TREE if we don't know how + to evaluate CODE at compile-time. */ + tree -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, + int overflowable) { - return int_const_binop_1 (code, arg1, arg2, 1); + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) + return tree_binop (code, arg1, arg2, overflowable); + + if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + return poly_int_binop (code, arg1, arg2, overflowable); + + return NULL_TREE; } /* Return true if binary operation OP distributes over addition in operand @@ -1925,7 +1948,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) /* Handle general case of two integer constants. For sizetype constant calculations we always want to know about overflow, even in the unsigned case. */ - tree res = int_const_binop_1 (code, arg0, arg1, -1); + tree res = int_const_binop (code, arg0, arg1, -1); if (res != NULL_TREE) return res; } diff --git a/gcc/fold-const.h b/gcc/fold-const.h index 4613a62e1f6..b921ba86854 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, tree, enum tree_code, tree, tree, tree, enum tree_code, tree, tree, tree *); extern tree fold_read_from_constant_string (tree); -extern tree int_const_binop (enum tree_code, const_tree, const_tree); +extern bool wide_int_binop (enum tree_code, wide_int &res, + const wide_int &arg1, const wide_int &arg2, + signop, wi::overflow_type &); +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); #define build_fold_addr_expr(T)\ build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) extern tree build_fold_addr_expr_loc (location_t, tree); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a7453abba7f..7764f7b30b6 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) return NULL_TREE; } -/* Wrapper around int_const_binop. Return true if we can compute the - result; i.e. if the operation doesn't overflow or if the overflow is - undefined. In the latter case (if the operation overflows and - overflow is undefined), then adjust the result to be -INF or +INF - depending on CODE, VAL1 and VAL2. Return the value in *RES. +/* Wrapper around wide_int_binop that adjusts for overflow. + + Return true if we can compute the result; i.e. if the operation + doesn't overflow or if the overflow is undefined. In the latter + case (if the operation overflows and overflow is undefined), then + adjust the result to be -INF or +INF depending on CODE, VAL1 and + VAL2. Return the value in *RES. Return false for division by zero, for which the result is indeterminate. */ @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) { wi::overflow_type overflow = wi::OVF_NONE; signop sign = TYPE_SIGN (TREE_TYPE (val1)); + wide_int w1 = wi::to_wide (val1); + wide_int w2 = wi::to_wide (val2); switch (code) { case RSHIFT_EXPR: case LSHIFT_EXPR: - { - wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); - if (wi::neg_p (wval2)) - { - wval2 = -wval2; - if (code == RSHIFT_EXPR) - code = LSHIFT_EXPR; - else - code = RSHIFT_EXPR; - } - - if (code == RSHIFT_EXPR) - /* It's unclear from the C standard whether shifts can overflow. - The following code ignores overflow; perhaps a C standard - interpretation ruling is needed. */ - *res = wi::rshift (wi::to_wide (val1), wval2, sign); - else - *res = wi::lshift (wi::to_wide (val1), wval2); - break; - } - + w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); + /* FALLTHRU */ case MULT_EXPR: - *res = wi::mul (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: - if (val2 == 0) - return false; - else - *res = wi::div_trunc (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case FLOOR_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_floor (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case CEIL_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_ceil (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case ROUND_DIV_EXPR: - if (val2 == 0) + if (!wide_int_binop (code, *res, w1, w2, sign, overflow)) return false; - *res = wi::div_round (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); break; default: gcc_unreachable (); } + /* If the operation overflowed return -INF or +INF depending on the + operation and the combination of signs of the operands. */ if (overflow && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) { - /* If the operation overflowed return -INF or +INF depending - on the operation and the combination of signs of the operands. */ - int sgn1 = tree_int_cst_sgn (val1); - int sgn2 = tree_int_cst_sgn (val2); + int sign1 = tree_int_cst_sgn (val1); + int sign2 = tree_int_cst_sgn (val2); /* Notice that we only need to handle the restricted set of operations handled by extract_range_from_binary_expr. @@ -1053,64 +1013,47 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) /* For multiplication, the sign of the overflow is given by the comparison of the signs of the operands. */ - if ((code == MULT_EXPR && sgn1 == sgn2) - /* For addition, the operands must be of the same sign - to yield an overflow. Its sign is therefore that - of one of the operands, for example the first. */ - || (code == PLUS_EXPR && sgn1 >= 0) - /* For subtraction, operands must be of - different signs to yield an overflow. Its sign is - therefore that of the first operand or the opposite of - that of the second operand. A first operand of 0 counts - as positive here, for the corner case 0 - (-INF), which - overflows, but must yield +INF. */ - || (code == MINUS_EXPR && sgn1 >= 0) + if ((code == MULT_EXPR && sign1 == sign2) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR || code == CEIL_DIV_EXPR || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) - *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); else - *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); return true; } return !overflow; } - -/* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO - bitmask if some bit is unset, it means for all numbers in the range +/* For range [LB, UB] compute two wide_int bitmasks. In *MAY_BE_NONZERO + bitmask, if some bit is unset, it means for all numbers in the range the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO - bitmask if some bit is set, it means for all numbers in the range + bitmask, if some bit is set, it means for all numbers in the range the bit is 1, otherwise it might be 0 or 1. */ -bool -zero_nonzero_bits_from_vr (const tree expr_type, - value_range *vr, - wide_int *may_be_nonzero, - wide_int *must_be_nonzero) +void +zero_nonzero_bits_from_bounds (signop sign, + const wide_int &lb, const wide_int &ub, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) { - *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); - *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); - if (!range_int_cst_p (vr)) - return false; + *may_be_nonzero = wi::minus_one (lb.get_precision ()); + *must_be_nonzero = wi::zero (lb.get_precision ()); - if (range_int_cst_singleton_p (vr)) + if (wi::eq_p (lb, ub)) { - *may_be_nonzero = wi::to_wide (vr->min); + *may_be_nonzero = lb; *must_be_nonzero = *may_be_nonzero; } - else if (tree_int_cst_sgn (vr->min) >= 0 - || tree_int_cst_sgn (vr->max) < 0) + else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) { - wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max); - *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max); - *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max); + wide_int xor_mask = lb ^ ub; + *may_be_nonzero = lb | ub; + *must_be_nonzero = lb & ub; if (xor_mask != 0) { wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, @@ -1119,7 +1062,26 @@ zero_nonzero_bits_from_vr (const tree expr_type, *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask); } } +} +/* Like zero_nonzero_bits_from_bounds, but use the range in value_range VR. */ + +bool +zero_nonzero_bits_from_vr (const tree expr_type, + value_range *vr, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) +{ + if (!range_int_cst_p (vr)) + { + *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); + *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); + return false; + } + + zero_nonzero_bits_from_bounds (TYPE_SIGN (expr_type), + wi::to_wide (vr->min), wi::to_wide (vr->max), + may_be_nonzero, must_be_nonzero); return true; } @@ -1275,6 +1237,52 @@ extract_range_from_multiplicative_op_1 (value_range *vr, wide_int_to_tree (type, max), NULL); } +/* For op & or | attempt to optimize: + + [LB, UB] op Z + into: + [LB op Z, UB op Z] + + if Z is a constant which (for op | its bitwise not) has n + consecutive least significant bits cleared followed by m 1 + consecutive bits set immediately above it and either + m + n == precision, or (x >> (m + n)) == (y >> (m + n)). + + The least significant n bits of all the values in the range are + cleared or set, the m bits above it are preserved and any bits + above these are required to be the same for all values in the + range. + + Return TRUE if the min and max can simply be folded. */ + +bool +range_easy_mask_min_max (tree_code code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask) + +{ + wide_int w = mask; + int m = 0, n = 0; + if (code == BIT_IOR_EXPR) + w = ~w; + if (wi::eq_p (w, 0)) + n = w.get_precision (); + else + { + n = wi::ctz (w); + w = ~(w | wi::mask (n, false, w.get_precision ())); + if (wi::eq_p (w, 0)) + m = w.get_precision () - n; + else + m = wi::ctz (w) - n; + } + wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); + if ((new_mask & lb) == (new_mask & ub)) + return true; + + return false; +} + /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -2175,39 +2183,14 @@ extract_range_from_binary_expr_1 (value_range *vr, vr1p = &vr0; } /* For op & or | attempt to optimize: - [x, y] op z into [x op z, y op z] - if z is a constant which (for op | its bitwise not) has n - consecutive least significant bits cleared followed by m 1 - consecutive bits set immediately above it and either - m + n == precision, or (x >> (m + n)) == (y >> (m + n)). - The least significant n bits of all the values in the range are - cleared or set, the m bits above it are preserved and any bits - above these are required to be the same for all values in the - range. */ - if (vr0p && range_int_cst_p (vr0p)) + [x, y] op z into [x op z, y op z]. */ + if (vr0p && range_int_cst_p (vr0p) + && range_easy_mask_min_max (code, wi::to_wide (vr0p->min), + wi::to_wide (vr0p->max), + wi::to_wide (vr1p->min))) { - wide_int w = wi::to_wide (vr1p->min); - int m = 0, n = 0; - if (code == BIT_IOR_EXPR) - w = ~w; - if (wi::eq_p (w, 0)) - n = TYPE_PRECISION (expr_type); - else - { - n = wi::ctz (w); - w = ~(w | wi::mask (n, false, w.get_precision ())); - if (wi::eq_p (w, 0)) - m = TYPE_PRECISION (expr_type) - n; - else - m = wi::ctz (w) - n; - } - wide_int mask = wi::mask (m + n, true, w.get_precision ()); - if ((mask & wi::to_wide (vr0p->min)) - == (mask & wi::to_wide (vr0p->max))) - { - min = int_const_binop (code, vr0p->min, vr1p->min); - max = int_const_binop (code, vr0p->max, vr1p->min); - } + min = int_const_binop (code, vr0p->min, vr1p->min); + max = int_const_binop (code, vr0p->max, vr1p->min); } } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 608ca5658b5..946e26e29b4 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -112,8 +112,14 @@ extern bool range_int_cst_p (value_range *); extern int operand_less_p (tree, tree); extern bool find_case_label_range (gswitch *, tree, tree, size_t *, size_t *); extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); +extern void zero_nonzero_bits_from_bounds (signop, const wide_int&, + const wide_int&, wide_int *, + wide_int *); extern bool zero_nonzero_bits_from_vr (const tree, value_range *, wide_int *, wide_int *); +extern bool range_easy_mask_min_max (tree_code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask); extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); extern bool range_int_cst_singleton_p (value_range *); extern int value_inside_range (tree, tree, tree);
On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > Hmmm, I think we can do better, and since this hasn't been reviewed yet, > I don't think anyone will mind the adjustment to the patch ;-). > > I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract > them into properly named poly_int_binop, wide_int_binop, and tree_binop, > and then use a default argument for int_const_binop() to get things going. > > Sorry for more changes in flight, but I thought we could benefit from > more cleanups :). > > OK for trunk pending tests? Much of GCC pre-dates function overloading / default args ;) Looks OK but can you please rename your tree_binop to int_cst_binop? Or maybe inline it into int_const_binop, also sharing the force_fit_type () tail with poly_int_binop? What about mixed INTEGER_CST / poly_int constants? Shouldn't it be if (neither-poly-nor-integer-cst (arg1 || arg2)) return NULL_TREE; if (poly_int_tree (arg1) || poly_int_tree (arg2)) poly-int-stuff else if (INTEGER_CST && INTEGER_CST) wide-int-stuff ? I see that is a pre-existing issue but if you are at refactoring... wi::to_poly_wide should handle INTEGER_CST operands just fine I hope. Thanks, Richard. > Aldy > > On 07/10/2018 04:31 AM, Aldy Hernandez wrote: > > Howdy! > > > > Attached are more cleanups to VRP getting rid of some repetitive code, > > as well as abstracting wide int handling code into their own functions. > > There should be no change to existing functionality. > > > > You may notice that I have removed the PLUS/MINUS_EXPR handling in > > vrp_int_const_binop, even from the new abstracted code: > > > > - /* For addition, the operands must be of the same sign > > - to yield an overflow. Its sign is therefore that > > - of one of the operands, for example the first. */ > > - || (code == PLUS_EXPR && sgn1 >= 0) > > - /* For subtraction, operands must be of > > - different signs to yield an overflow. Its sign is > > - therefore that of the first operand or the opposite of > > - that of the second operand. A first operand of 0 counts > > - as positive here, for the corner case 0 - (-INF), which > > - overflows, but must yield +INF. */ > > - || (code == MINUS_EXPR && sgn1 >= 0) > > > > This code is actually unreachable, as the switch above this snippet was > > already aborting if code was not one of the shift or mult/div operators. > > > > Oh yeah, don't blame me for the cryptic comment to > > range_easy_mask_min_mask(). That machine language comment was already > > there ;-). > > > > OK pending one more round of tests? > > > > Aldy
On 07/11/2018 08:52 AM, Richard Biener wrote: > On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >> >> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >> I don't think anyone will mind the adjustment to the patch ;-). >> >> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >> and then use a default argument for int_const_binop() to get things going. >> >> Sorry for more changes in flight, but I thought we could benefit from >> more cleanups :). >> >> OK for trunk pending tests? > > Much of GCC pre-dates function overloading / default args ;) Heh...and ANSI C. > > Looks OK but can you please rename your tree_binop to int_cst_binop? > Or maybe inline it into int_const_binop, also sharing the force_fit_type () > tail with poly_int_binop? I tried both, but inlining looked cleaner :). Done. > > What about mixed INTEGER_CST / poly_int constants? Shouldn't it > be > > if (neither-poly-nor-integer-cst (arg1 || arg2)) > return NULL_TREE; > if (poly_int_tree (arg1) || poly_int_tree (arg2)) > poly-int-stuff > else if (INTEGER_CST && INTEGER_CST) > wide-int-stuff > > ? I see that is a pre-existing issue but if you are at refactoring... > wi::to_poly_wide should handle INTEGER_CST operands just fine > I hope. This aborted: gcc_assert (NUM_POLY_INT_COEFFS != 1); but even taking it out made the bootstrap die somewhere else. If it's ok, I'd rather not tackle this now, as I have some more cleanups that are pending on this. If you feel strongly, I could do it at a later time. OK pending tests? Aldy gcc/ * fold-const.c (int_const_binop_1): Abstract... (wide_int_binop): ...wide int code here. (poly_int_binop): ...poly int code here. Abstract the rest of int_const_binop_1 into int_const_binop. * fold-const.h (wide_int_binop): New. * tree-vrp.c (vrp_int_const_binop): Call wide_int_binop. Remove useless PLUS/MINUS_EXPR case. (zero_nonzero_bits_from_vr): Move wide int code... (zero_nonzero_bits_from_bounds): ...here. (extract_range_from_binary_expr_1): Move mask optimization code... (range_easy_mask_min_max): ...here. * tree-vrp.h (zero_nonzero_bits_from_bounds): New. (range_easy_mask_min_max): New. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 97c435fa5e0..ad8c0a69f63 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -966,21 +966,17 @@ int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2 && TYPE_MODE (type1) == TYPE_MODE (type2); } -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce + a new constant in RES. Return FALSE if we don't know how to + evaluate CODE at compile-time. */ -static tree -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, - int overflowable) +bool +wide_int_binop (enum tree_code code, + wide_int &res, const wide_int &arg1, const wide_int &arg2, + signop sign, wi::overflow_type &overflow) { - wide_int res; - tree t; - tree type = TREE_TYPE (parg1); - signop sign = TYPE_SIGN (type); - wi::overflow_type overflow = wi::OVF_NONE; - - wi::tree_to_wide_ref arg1 = wi::to_wide (parg1); - wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); - + wide_int tmp; + overflow = wi::OVF_NONE; switch (code) { case BIT_IOR_EXPR: @@ -999,37 +995,41 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case LSHIFT_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RSHIFT_EXPR) code = LSHIFT_EXPR; else code = RSHIFT_EXPR; } + else + tmp = arg2; if (code == RSHIFT_EXPR) /* It's unclear from the C standard whether shifts can overflow. The following code ignores overflow; perhaps a C standard interpretation ruling is needed. */ - res = wi::rshift (arg1, arg2, sign); + res = wi::rshift (arg1, tmp, sign); else - res = wi::lshift (arg1, arg2); + res = wi::lshift (arg1, tmp); break; case RROTATE_EXPR: case LROTATE_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RROTATE_EXPR) code = LROTATE_EXPR; else code = RROTATE_EXPR; } + else + tmp = arg2; if (code == RROTATE_EXPR) - res = wi::rrotate (arg1, arg2); + res = wi::rrotate (arg1, tmp); else - res = wi::lrotate (arg1, arg2); + res = wi::lrotate (arg1, tmp); break; case PLUS_EXPR: @@ -1051,49 +1051,49 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_floor (arg1, arg2, sign, &overflow); break; case CEIL_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_ceil (arg1, arg2, sign, &overflow); break; case ROUND_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_round (arg1, arg2, sign, &overflow); break; case TRUNC_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_floor (arg1, arg2, sign, &overflow); break; case CEIL_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_ceil (arg1, arg2, sign, &overflow); break; case ROUND_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_round (arg1, arg2, sign, &overflow); break; @@ -1106,89 +1106,94 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, break; default: - return NULL_TREE; + return false; } - - t = force_fit_type (type, res, overflowable, - (((sign == SIGNED || overflowable == -1) - && overflow) - | TREE_OVERFLOW (parg1) | TREE_OVERFLOW (parg2))); - - return t; + return true; } -/* Combine two integer constants PARG1 and PARG2 under operation CODE - to produce a new constant. Return NULL_TREE if we don't know how +/* Combine two poly int's ARG1 and ARG2 under operation CODE to + produce a new constant in RES. Return FALSE if we don't know how to evaluate CODE at compile-time. */ -static tree -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, - int overflowable) +static bool +poly_int_binop (poly_wide_int &res, enum tree_code code, + const_tree arg1, const_tree arg2, + signop sign, wi::overflow_type &overflow) { - if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) - return int_const_binop_2 (code, arg1, arg2, overflowable); - gcc_assert (NUM_POLY_INT_COEFFS != 1); - - if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + gcc_assert (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)); + switch (code) { - poly_wide_int res; - wi::overflow_type overflow; - tree type = TREE_TYPE (arg1); - signop sign = TYPE_SIGN (type); - switch (code) - { - case PLUS_EXPR: - res = wi::add (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case PLUS_EXPR: + res = wi::add (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MINUS_EXPR: - res = wi::sub (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case MINUS_EXPR: + res = wi::sub (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MULT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg1), - wi::to_wide (arg2), sign, &overflow); - else if (TREE_CODE (arg1) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg2), - wi::to_wide (arg1), sign, &overflow); - else - return NULL_TREE; - break; + case MULT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg1), + wi::to_wide (arg2), sign, &overflow); + else if (TREE_CODE (arg1) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg2), + wi::to_wide (arg1), sign, &overflow); + else + return NULL_TREE; + break; - case LSHIFT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); - else - return NULL_TREE; - break; + case LSHIFT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); + else + return false; + break; - case BIT_IOR_EXPR: - if (TREE_CODE (arg2) != INTEGER_CST - || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), - &res)) - return NULL_TREE; - break; + case BIT_IOR_EXPR: + if (TREE_CODE (arg2) != INTEGER_CST + || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), + &res)) + return false; + break; - default: - return NULL_TREE; - } - return force_fit_type (type, res, overflowable, - (((sign == SIGNED || overflowable == -1) - && overflow) - | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); + default: + return false; } - - return NULL_TREE; + return true; } +/* Combine two integer constants PARG1 and PARG2 under operation CODE + to produce a new constant. Return NULL_TREE if we don't know how + to evaluate CODE at compile-time. */ + tree -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, + int overflowable) { - return int_const_binop_1 (code, arg1, arg2, 1); + bool success = false; + poly_wide_int poly_res; + tree type = TREE_TYPE (arg1); + signop sign = TYPE_SIGN (type); + wi::overflow_type overflow = wi::OVF_NONE; + + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) + { + wide_int warg1 = wi::to_wide (arg1), res; + wide_int warg2 = wi::to_wide (arg2, TYPE_PRECISION (type)); + success = wide_int_binop (code, res, warg1, warg2, sign, overflow); + poly_res = res; + } + else if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + success = poly_int_binop (poly_res, code, arg1, arg2, sign, overflow); + if (success) + return force_fit_type (type, poly_res, overflowable, + (((sign == SIGNED || overflowable == -1) + && overflow) + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); + return NULL_TREE; } /* Return true if binary operation OP distributes over addition in operand @@ -1925,7 +1930,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) /* Handle general case of two integer constants. For sizetype constant calculations we always want to know about overflow, even in the unsigned case. */ - tree res = int_const_binop_1 (code, arg0, arg1, -1); + tree res = int_const_binop (code, arg0, arg1, -1); if (res != NULL_TREE) return res; } diff --git a/gcc/fold-const.h b/gcc/fold-const.h index 4613a62e1f6..b921ba86854 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, tree, enum tree_code, tree, tree, tree, enum tree_code, tree, tree, tree *); extern tree fold_read_from_constant_string (tree); -extern tree int_const_binop (enum tree_code, const_tree, const_tree); +extern bool wide_int_binop (enum tree_code, wide_int &res, + const wide_int &arg1, const wide_int &arg2, + signop, wi::overflow_type &); +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); #define build_fold_addr_expr(T)\ build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) extern tree build_fold_addr_expr_loc (location_t, tree); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a7453abba7f..7764f7b30b6 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) return NULL_TREE; } -/* Wrapper around int_const_binop. Return true if we can compute the - result; i.e. if the operation doesn't overflow or if the overflow is - undefined. In the latter case (if the operation overflows and - overflow is undefined), then adjust the result to be -INF or +INF - depending on CODE, VAL1 and VAL2. Return the value in *RES. +/* Wrapper around wide_int_binop that adjusts for overflow. + + Return true if we can compute the result; i.e. if the operation + doesn't overflow or if the overflow is undefined. In the latter + case (if the operation overflows and overflow is undefined), then + adjust the result to be -INF or +INF depending on CODE, VAL1 and + VAL2. Return the value in *RES. Return false for division by zero, for which the result is indeterminate. */ @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) { wi::overflow_type overflow = wi::OVF_NONE; signop sign = TYPE_SIGN (TREE_TYPE (val1)); + wide_int w1 = wi::to_wide (val1); + wide_int w2 = wi::to_wide (val2); switch (code) { case RSHIFT_EXPR: case LSHIFT_EXPR: - { - wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); - if (wi::neg_p (wval2)) - { - wval2 = -wval2; - if (code == RSHIFT_EXPR) - code = LSHIFT_EXPR; - else - code = RSHIFT_EXPR; - } - - if (code == RSHIFT_EXPR) - /* It's unclear from the C standard whether shifts can overflow. - The following code ignores overflow; perhaps a C standard - interpretation ruling is needed. */ - *res = wi::rshift (wi::to_wide (val1), wval2, sign); - else - *res = wi::lshift (wi::to_wide (val1), wval2); - break; - } - + w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); + /* FALLTHRU */ case MULT_EXPR: - *res = wi::mul (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: - if (val2 == 0) - return false; - else - *res = wi::div_trunc (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case FLOOR_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_floor (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case CEIL_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_ceil (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case ROUND_DIV_EXPR: - if (val2 == 0) + if (!wide_int_binop (code, *res, w1, w2, sign, overflow)) return false; - *res = wi::div_round (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); break; default: gcc_unreachable (); } + /* If the operation overflowed return -INF or +INF depending on the + operation and the combination of signs of the operands. */ if (overflow && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) { - /* If the operation overflowed return -INF or +INF depending - on the operation and the combination of signs of the operands. */ - int sgn1 = tree_int_cst_sgn (val1); - int sgn2 = tree_int_cst_sgn (val2); + int sign1 = tree_int_cst_sgn (val1); + int sign2 = tree_int_cst_sgn (val2); /* Notice that we only need to handle the restricted set of operations handled by extract_range_from_binary_expr. @@ -1053,64 +1013,47 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) /* For multiplication, the sign of the overflow is given by the comparison of the signs of the operands. */ - if ((code == MULT_EXPR && sgn1 == sgn2) - /* For addition, the operands must be of the same sign - to yield an overflow. Its sign is therefore that - of one of the operands, for example the first. */ - || (code == PLUS_EXPR && sgn1 >= 0) - /* For subtraction, operands must be of - different signs to yield an overflow. Its sign is - therefore that of the first operand or the opposite of - that of the second operand. A first operand of 0 counts - as positive here, for the corner case 0 - (-INF), which - overflows, but must yield +INF. */ - || (code == MINUS_EXPR && sgn1 >= 0) + if ((code == MULT_EXPR && sign1 == sign2) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR || code == CEIL_DIV_EXPR || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) - *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); else - *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); return true; } return !overflow; } - -/* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO - bitmask if some bit is unset, it means for all numbers in the range +/* For range [LB, UB] compute two wide_int bitmasks. In *MAY_BE_NONZERO + bitmask, if some bit is unset, it means for all numbers in the range the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO - bitmask if some bit is set, it means for all numbers in the range + bitmask, if some bit is set, it means for all numbers in the range the bit is 1, otherwise it might be 0 or 1. */ -bool -zero_nonzero_bits_from_vr (const tree expr_type, - value_range *vr, - wide_int *may_be_nonzero, - wide_int *must_be_nonzero) +void +zero_nonzero_bits_from_bounds (signop sign, + const wide_int &lb, const wide_int &ub, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) { - *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); - *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); - if (!range_int_cst_p (vr)) - return false; + *may_be_nonzero = wi::minus_one (lb.get_precision ()); + *must_be_nonzero = wi::zero (lb.get_precision ()); - if (range_int_cst_singleton_p (vr)) + if (wi::eq_p (lb, ub)) { - *may_be_nonzero = wi::to_wide (vr->min); + *may_be_nonzero = lb; *must_be_nonzero = *may_be_nonzero; } - else if (tree_int_cst_sgn (vr->min) >= 0 - || tree_int_cst_sgn (vr->max) < 0) + else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) { - wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max); - *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max); - *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max); + wide_int xor_mask = lb ^ ub; + *may_be_nonzero = lb | ub; + *must_be_nonzero = lb & ub; if (xor_mask != 0) { wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, @@ -1119,7 +1062,26 @@ zero_nonzero_bits_from_vr (const tree expr_type, *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask); } } +} +/* Like zero_nonzero_bits_from_bounds, but use the range in value_range VR. */ + +bool +zero_nonzero_bits_from_vr (const tree expr_type, + value_range *vr, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) +{ + if (!range_int_cst_p (vr)) + { + *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); + *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); + return false; + } + + zero_nonzero_bits_from_bounds (TYPE_SIGN (expr_type), + wi::to_wide (vr->min), wi::to_wide (vr->max), + may_be_nonzero, must_be_nonzero); return true; } @@ -1275,6 +1237,52 @@ extract_range_from_multiplicative_op_1 (value_range *vr, wide_int_to_tree (type, max), NULL); } +/* For op & or | attempt to optimize: + + [LB, UB] op Z + into: + [LB op Z, UB op Z] + + if Z is a constant which (for op | its bitwise not) has n + consecutive least significant bits cleared followed by m 1 + consecutive bits set immediately above it and either + m + n == precision, or (x >> (m + n)) == (y >> (m + n)). + + The least significant n bits of all the values in the range are + cleared or set, the m bits above it are preserved and any bits + above these are required to be the same for all values in the + range. + + Return TRUE if the min and max can simply be folded. */ + +bool +range_easy_mask_min_max (tree_code code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask) + +{ + wide_int w = mask; + int m = 0, n = 0; + if (code == BIT_IOR_EXPR) + w = ~w; + if (wi::eq_p (w, 0)) + n = w.get_precision (); + else + { + n = wi::ctz (w); + w = ~(w | wi::mask (n, false, w.get_precision ())); + if (wi::eq_p (w, 0)) + m = w.get_precision () - n; + else + m = wi::ctz (w) - n; + } + wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); + if ((new_mask & lb) == (new_mask & ub)) + return true; + + return false; +} + /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -2175,39 +2183,14 @@ extract_range_from_binary_expr_1 (value_range *vr, vr1p = &vr0; } /* For op & or | attempt to optimize: - [x, y] op z into [x op z, y op z] - if z is a constant which (for op | its bitwise not) has n - consecutive least significant bits cleared followed by m 1 - consecutive bits set immediately above it and either - m + n == precision, or (x >> (m + n)) == (y >> (m + n)). - The least significant n bits of all the values in the range are - cleared or set, the m bits above it are preserved and any bits - above these are required to be the same for all values in the - range. */ - if (vr0p && range_int_cst_p (vr0p)) + [x, y] op z into [x op z, y op z]. */ + if (vr0p && range_int_cst_p (vr0p) + && range_easy_mask_min_max (code, wi::to_wide (vr0p->min), + wi::to_wide (vr0p->max), + wi::to_wide (vr1p->min))) { - wide_int w = wi::to_wide (vr1p->min); - int m = 0, n = 0; - if (code == BIT_IOR_EXPR) - w = ~w; - if (wi::eq_p (w, 0)) - n = TYPE_PRECISION (expr_type); - else - { - n = wi::ctz (w); - w = ~(w | wi::mask (n, false, w.get_precision ())); - if (wi::eq_p (w, 0)) - m = TYPE_PRECISION (expr_type) - n; - else - m = wi::ctz (w) - n; - } - wide_int mask = wi::mask (m + n, true, w.get_precision ()); - if ((mask & wi::to_wide (vr0p->min)) - == (mask & wi::to_wide (vr0p->max))) - { - min = int_const_binop (code, vr0p->min, vr1p->min); - max = int_const_binop (code, vr0p->max, vr1p->min); - } + min = int_const_binop (code, vr0p->min, vr1p->min); + max = int_const_binop (code, vr0p->max, vr1p->min); } } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 608ca5658b5..946e26e29b4 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -112,8 +112,14 @@ extern bool range_int_cst_p (value_range *); extern int operand_less_p (tree, tree); extern bool find_case_label_range (gswitch *, tree, tree, size_t *, size_t *); extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); +extern void zero_nonzero_bits_from_bounds (signop, const wide_int&, + const wide_int&, wide_int *, + wide_int *); extern bool zero_nonzero_bits_from_vr (const tree, value_range *, wide_int *, wide_int *); +extern bool range_easy_mask_min_max (tree_code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask); extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); extern bool range_int_cst_singleton_p (value_range *); extern int value_inside_range (tree, tree, tree);
Richard Biener <richard.guenther@gmail.com> writes: > On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >> >> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >> I don't think anyone will mind the adjustment to the patch ;-). >> >> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >> and then use a default argument for int_const_binop() to get things going. >> >> Sorry for more changes in flight, but I thought we could benefit from >> more cleanups :). >> >> OK for trunk pending tests? > > Much of GCC pre-dates function overloading / default args ;) > > Looks OK but can you please rename your tree_binop to int_cst_binop? > Or maybe inline it into int_const_binop, also sharing the force_fit_type () > tail with poly_int_binop? > > What about mixed INTEGER_CST / poly_int constants? Shouldn't it > be > > if (neither-poly-nor-integer-cst (arg1 || arg2)) > return NULL_TREE; > if (poly_int_tree (arg1) || poly_int_tree (arg2)) > poly-int-stuff > else if (INTEGER_CST && INTEGER_CST) > wide-int-stuff > > ? I see that is a pre-existing issue but if you are at refactoring... > wi::to_poly_wide should handle INTEGER_CST operands just fine > I hope. Don't think it's a preexisting issue. poly_int_tree_p returns true for anything that can be represented as a poly_int, i.e. both INTEGER_CST and POLY_INT_CST. (It wouldn't really make sense to ask whether something could *only* be represented as a POLY_INT_CST.) So: if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) { poly_wide_int res; bool overflow; tree type = TREE_TYPE (arg1); signop sign = TYPE_SIGN (type); switch (code) { case PLUS_EXPR: res = wi::add (wi::to_poly_wide (arg1), wi::to_poly_wide (arg2), sign, &overflow); break; handles POLY_INT_CST + POLY_INT_CST, POLY_INT_CST + INTEGER_CST and INTEGER_CST + POLY_INT_CST. Thanks, Richard
Aldy Hernandez <aldyh@redhat.com> writes: > On 07/11/2018 08:52 AM, Richard Biener wrote: >> On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >>> >>> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >>> I don't think anyone will mind the adjustment to the patch ;-). >>> >>> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >>> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >>> and then use a default argument for int_const_binop() to get things going. >>> >>> Sorry for more changes in flight, but I thought we could benefit from >>> more cleanups :). >>> >>> OK for trunk pending tests? >> >> Much of GCC pre-dates function overloading / default args ;) > > Heh...and ANSI C. > >> >> Looks OK but can you please rename your tree_binop to int_cst_binop? >> Or maybe inline it into int_const_binop, also sharing the force_fit_type () >> tail with poly_int_binop? > > I tried both, but inlining looked cleaner :). Done. > >> >> What about mixed INTEGER_CST / poly_int constants? Shouldn't it >> be >> >> if (neither-poly-nor-integer-cst (arg1 || arg2)) >> return NULL_TREE; >> if (poly_int_tree (arg1) || poly_int_tree (arg2)) >> poly-int-stuff >> else if (INTEGER_CST && INTEGER_CST) >> wide-int-stuff >> >> ? I see that is a pre-existing issue but if you are at refactoring... >> wi::to_poly_wide should handle INTEGER_CST operands just fine >> I hope. > > This aborted: > gcc_assert (NUM_POLY_INT_COEFFS != 1); > > but even taking it out made the bootstrap die somewhere else. > > If it's ok, I'd rather not tackle this now, as I have some more cleanups > that are pending on this. If you feel strongly, I could do it at a > later time. > > OK pending tests? LGTM FWIW, just some nits: > -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ > +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce > + a new constant in RES. Return FALSE if we don't know how to > + evaluate CODE at compile-time. */ > > -static tree > -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, > - int overflowable) > +bool > +wide_int_binop (enum tree_code code, > + wide_int &res, const wide_int &arg1, const wide_int &arg2, > + signop sign, wi::overflow_type &overflow) > { IMO we should avoid pass-back by reference like the plague. :-) It's especially confusing when the code does things like: case FLOOR_DIV_EXPR: if (arg2 == 0) return false; res = wi::div_floor (arg1, arg2, sign, &overflow); break; It looked at first like it was taking the address of a local variable and failing to propagate the information back up. I think we should stick to using pointers for this kind of thing. > -/* Combine two integer constants PARG1 and PARG2 under operation CODE > - to produce a new constant. Return NULL_TREE if we don't know how > +/* Combine two poly int's ARG1 and ARG2 under operation CODE to > + produce a new constant in RES. Return FALSE if we don't know how > to evaluate CODE at compile-time. */ > > -static tree > -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, > - int overflowable) > +static bool > +poly_int_binop (poly_wide_int &res, enum tree_code code, > + const_tree arg1, const_tree arg2, > + signop sign, wi::overflow_type &overflow) > { Would be good to be consistent about the order of the result and code arguments. Here it's "result, code" (which seems better IMO), but in wide_int_binop it's "code, result". > +/* Combine two integer constants PARG1 and PARG2 under operation CODE > + to produce a new constant. Return NULL_TREE if we don't know how > + to evaluate CODE at compile-time. */ > + > tree > -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) > +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, > + int overflowable) s/PARG/ARG/g in comment. > { > - return int_const_binop_1 (code, arg1, arg2, 1); > + bool success = false; > + poly_wide_int poly_res; > + tree type = TREE_TYPE (arg1); > + signop sign = TYPE_SIGN (type); > + wi::overflow_type overflow = wi::OVF_NONE; > + > + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) > + { > + wide_int warg1 = wi::to_wide (arg1), res; > + wide_int warg2 = wi::to_wide (arg2, TYPE_PRECISION (type)); > + success = wide_int_binop (code, res, warg1, warg2, sign, overflow); > + poly_res = res; > + } > + else if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) > + success = poly_int_binop (poly_res, code, arg1, arg2, sign, overflow); > + if (success) > + return force_fit_type (type, poly_res, overflowable, > + (((sign == SIGNED || overflowable == -1) > + && overflow) > + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); > + return NULL_TREE; > } > > /* Return true if binary operation OP distributes over addition in operand > @@ -1925,7 +1930,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) > /* Handle general case of two integer constants. For sizetype > constant calculations we always want to know about overflow, > even in the unsigned case. */ > - tree res = int_const_binop_1 (code, arg0, arg1, -1); > + tree res = int_const_binop (code, arg0, arg1, -1); > if (res != NULL_TREE) > return res; > } > diff --git a/gcc/fold-const.h b/gcc/fold-const.h > index 4613a62e1f6..b921ba86854 100644 > --- a/gcc/fold-const.h > +++ b/gcc/fold-const.h > @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, > tree, enum tree_code, tree, tree, > tree, enum tree_code, tree, tree, tree *); > extern tree fold_read_from_constant_string (tree); > -extern tree int_const_binop (enum tree_code, const_tree, const_tree); > +extern bool wide_int_binop (enum tree_code, wide_int &res, > + const wide_int &arg1, const wide_int &arg2, > + signop, wi::overflow_type &); > +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); > #define build_fold_addr_expr(T)\ > build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) > extern tree build_fold_addr_expr_loc (location_t, tree); > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index a7453abba7f..7764f7b30b6 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) > return NULL_TREE; > } > > -/* Wrapper around int_const_binop. Return true if we can compute the > - result; i.e. if the operation doesn't overflow or if the overflow is > - undefined. In the latter case (if the operation overflows and > - overflow is undefined), then adjust the result to be -INF or +INF > - depending on CODE, VAL1 and VAL2. Return the value in *RES. > +/* Wrapper around wide_int_binop that adjusts for overflow. > + > + Return true if we can compute the result; i.e. if the operation > + doesn't overflow or if the overflow is undefined. In the latter > + case (if the operation overflows and overflow is undefined), then > + adjust the result to be -INF or +INF depending on CODE, VAL1 and > + VAL2. Return the value in *RES. > > Return false for division by zero, for which the result is > indeterminate. */ > @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) > { > wi::overflow_type overflow = wi::OVF_NONE; > signop sign = TYPE_SIGN (TREE_TYPE (val1)); > + wide_int w1 = wi::to_wide (val1); > + wide_int w2 = wi::to_wide (val2); > This doesn't come for free. Until we can use "auto", it might be better to keep the wi::to_wide calls at the point they're used. That probably maans having a separate call to wide_int_binop for shifts. Thanks, Richard
On 07/11/2018 01:33 PM, Richard Sandiford wrote: > Aldy Hernandez <aldyh@redhat.com> writes: >> On 07/11/2018 08:52 AM, Richard Biener wrote: >>> On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >>>> >>>> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >>>> I don't think anyone will mind the adjustment to the patch ;-). >>>> >>>> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >>>> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >>>> and then use a default argument for int_const_binop() to get things going. >>>> >>>> Sorry for more changes in flight, but I thought we could benefit from >>>> more cleanups :). >>>> >>>> OK for trunk pending tests? >>> >>> Much of GCC pre-dates function overloading / default args ;) >> >> Heh...and ANSI C. >> >>> >>> Looks OK but can you please rename your tree_binop to int_cst_binop? >>> Or maybe inline it into int_const_binop, also sharing the force_fit_type () >>> tail with poly_int_binop? >> >> I tried both, but inlining looked cleaner :). Done. >> >>> >>> What about mixed INTEGER_CST / poly_int constants? Shouldn't it >>> be >>> >>> if (neither-poly-nor-integer-cst (arg1 || arg2)) >>> return NULL_TREE; >>> if (poly_int_tree (arg1) || poly_int_tree (arg2)) >>> poly-int-stuff >>> else if (INTEGER_CST && INTEGER_CST) >>> wide-int-stuff >>> >>> ? I see that is a pre-existing issue but if you are at refactoring... >>> wi::to_poly_wide should handle INTEGER_CST operands just fine >>> I hope. >> >> This aborted: >> gcc_assert (NUM_POLY_INT_COEFFS != 1); >> >> but even taking it out made the bootstrap die somewhere else. >> >> If it's ok, I'd rather not tackle this now, as I have some more cleanups >> that are pending on this. If you feel strongly, I could do it at a >> later time. >> >> OK pending tests? > > LGTM FWIW, just some nits: > >> -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ >> +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce >> + a new constant in RES. Return FALSE if we don't know how to >> + evaluate CODE at compile-time. */ >> >> -static tree >> -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, >> - int overflowable) >> +bool >> +wide_int_binop (enum tree_code code, >> + wide_int &res, const wide_int &arg1, const wide_int &arg2, >> + signop sign, wi::overflow_type &overflow) >> { > > IMO we should avoid pass-back by reference like the plague. :-) > It's especially confusing when the code does things like: > > case FLOOR_DIV_EXPR: > if (arg2 == 0) > return false; > res = wi::div_floor (arg1, arg2, sign, &overflow); > break; > > It looked at first like it was taking the address of a local variable > and failing to propagate the information back up. > > I think we should stick to using pointers for this kind of thing. > Hmmm, I kinda like them. It just takes some getting used to, but generally yields cleaner code as you don't have to keep using '*' everywhere. Plus, the callee can assume the pointer is non-zero. >> -/* Combine two integer constants PARG1 and PARG2 under operation CODE >> - to produce a new constant. Return NULL_TREE if we don't know how >> +/* Combine two poly int's ARG1 and ARG2 under operation CODE to >> + produce a new constant in RES. Return FALSE if we don't know how >> to evaluate CODE at compile-time. */ >> >> -static tree >> -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, >> - int overflowable) >> +static bool >> +poly_int_binop (poly_wide_int &res, enum tree_code code, >> + const_tree arg1, const_tree arg2, >> + signop sign, wi::overflow_type &overflow) >> { > > Would be good to be consistent about the order of the result and code > arguments. Here it's "result, code" (which seems better IMO), > but in wide_int_binop it's "code, result". Agreed. Fixed. > >> +/* Combine two integer constants PARG1 and PARG2 under operation CODE >> + to produce a new constant. Return NULL_TREE if we don't know how >> + to evaluate CODE at compile-time. */ >> + >> tree >> -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) >> +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, >> + int overflowable) > > s/PARG/ARG/g in comment. Fixed. > >> { >> - return int_const_binop_1 (code, arg1, arg2, 1); >> + bool success = false; >> + poly_wide_int poly_res; >> + tree type = TREE_TYPE (arg1); >> + signop sign = TYPE_SIGN (type); >> + wi::overflow_type overflow = wi::OVF_NONE; >> + >> + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) >> + { >> + wide_int warg1 = wi::to_wide (arg1), res; >> + wide_int warg2 = wi::to_wide (arg2, TYPE_PRECISION (type)); >> + success = wide_int_binop (code, res, warg1, warg2, sign, overflow); >> + poly_res = res; >> + } >> + else if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) >> + success = poly_int_binop (poly_res, code, arg1, arg2, sign, overflow); >> + if (success) >> + return force_fit_type (type, poly_res, overflowable, >> + (((sign == SIGNED || overflowable == -1) >> + && overflow) >> + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); >> + return NULL_TREE; >> } >> >> /* Return true if binary operation OP distributes over addition in operand >> @@ -1925,7 +1930,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) >> /* Handle general case of two integer constants. For sizetype >> constant calculations we always want to know about overflow, >> even in the unsigned case. */ >> - tree res = int_const_binop_1 (code, arg0, arg1, -1); >> + tree res = int_const_binop (code, arg0, arg1, -1); >> if (res != NULL_TREE) >> return res; >> } >> diff --git a/gcc/fold-const.h b/gcc/fold-const.h >> index 4613a62e1f6..b921ba86854 100644 >> --- a/gcc/fold-const.h >> +++ b/gcc/fold-const.h >> @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, >> tree, enum tree_code, tree, tree, >> tree, enum tree_code, tree, tree, tree *); >> extern tree fold_read_from_constant_string (tree); >> -extern tree int_const_binop (enum tree_code, const_tree, const_tree); >> +extern bool wide_int_binop (enum tree_code, wide_int &res, >> + const wide_int &arg1, const wide_int &arg2, >> + signop, wi::overflow_type &); >> +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); >> #define build_fold_addr_expr(T)\ >> build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) >> extern tree build_fold_addr_expr_loc (location_t, tree); >> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c >> index a7453abba7f..7764f7b30b6 100644 >> --- a/gcc/tree-vrp.c >> +++ b/gcc/tree-vrp.c >> @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) >> return NULL_TREE; >> } >> >> -/* Wrapper around int_const_binop. Return true if we can compute the >> - result; i.e. if the operation doesn't overflow or if the overflow is >> - undefined. In the latter case (if the operation overflows and >> - overflow is undefined), then adjust the result to be -INF or +INF >> - depending on CODE, VAL1 and VAL2. Return the value in *RES. >> +/* Wrapper around wide_int_binop that adjusts for overflow. >> + >> + Return true if we can compute the result; i.e. if the operation >> + doesn't overflow or if the overflow is undefined. In the latter >> + case (if the operation overflows and overflow is undefined), then >> + adjust the result to be -INF or +INF depending on CODE, VAL1 and >> + VAL2. Return the value in *RES. >> >> Return false for division by zero, for which the result is >> indeterminate. */ >> @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) >> { >> wi::overflow_type overflow = wi::OVF_NONE; >> signop sign = TYPE_SIGN (TREE_TYPE (val1)); >> + wide_int w1 = wi::to_wide (val1); >> + wide_int w2 = wi::to_wide (val2); >> > > This doesn't come for free. Until we can use "auto", it might be better > to keep the wi::to_wide calls at the point they're used. That probably > maans having a separate call to wide_int_binop for shifts. I would prefer cleaner rather than saving a few microseconds or bytes, unless it's in the critical path. This particular code doesn't seem to be ??. Thanks for the review! Aldy gcc/ * fold-const.c (int_const_binop_1): Abstract... (wide_int_binop): ...wide int code here. (poly_int_binop): ...poly int code here. Abstract the rest of int_const_binop_1 into int_const_binop. * fold-const.h (wide_int_binop): New. * tree-vrp.c (vrp_int_const_binop): Call wide_int_binop. Remove useless PLUS/MINUS_EXPR case. (zero_nonzero_bits_from_vr): Move wide int code... (zero_nonzero_bits_from_bounds): ...here. (extract_range_from_binary_expr_1): Move mask optimization code... (range_easy_mask_min_max): ...here. * tree-vrp.h (zero_nonzero_bits_from_bounds): New. (range_easy_mask_min_max): New. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 97c435fa5e0..5d5e0a9621f 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -966,21 +966,17 @@ int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2 && TYPE_MODE (type1) == TYPE_MODE (type2); } -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce + a new constant in RES. Return FALSE if we don't know how to + evaluate CODE at compile-time. */ -static tree -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, - int overflowable) +bool +wide_int_binop (wide_int &res, + enum tree_code code, const wide_int &arg1, const wide_int &arg2, + signop sign, wi::overflow_type &overflow) { - wide_int res; - tree t; - tree type = TREE_TYPE (parg1); - signop sign = TYPE_SIGN (type); - wi::overflow_type overflow = wi::OVF_NONE; - - wi::tree_to_wide_ref arg1 = wi::to_wide (parg1); - wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); - + wide_int tmp; + overflow = wi::OVF_NONE; switch (code) { case BIT_IOR_EXPR: @@ -999,37 +995,41 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case LSHIFT_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RSHIFT_EXPR) code = LSHIFT_EXPR; else code = RSHIFT_EXPR; } + else + tmp = arg2; if (code == RSHIFT_EXPR) /* It's unclear from the C standard whether shifts can overflow. The following code ignores overflow; perhaps a C standard interpretation ruling is needed. */ - res = wi::rshift (arg1, arg2, sign); + res = wi::rshift (arg1, tmp, sign); else - res = wi::lshift (arg1, arg2); + res = wi::lshift (arg1, tmp); break; case RROTATE_EXPR: case LROTATE_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RROTATE_EXPR) code = LROTATE_EXPR; else code = RROTATE_EXPR; } + else + tmp = arg2; if (code == RROTATE_EXPR) - res = wi::rrotate (arg1, arg2); + res = wi::rrotate (arg1, tmp); else - res = wi::lrotate (arg1, arg2); + res = wi::lrotate (arg1, tmp); break; case PLUS_EXPR: @@ -1051,49 +1051,49 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_floor (arg1, arg2, sign, &overflow); break; case CEIL_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_ceil (arg1, arg2, sign, &overflow); break; case ROUND_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_round (arg1, arg2, sign, &overflow); break; case TRUNC_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_floor (arg1, arg2, sign, &overflow); break; case CEIL_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_ceil (arg1, arg2, sign, &overflow); break; case ROUND_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_round (arg1, arg2, sign, &overflow); break; @@ -1106,89 +1106,94 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, break; default: - return NULL_TREE; + return false; } - - t = force_fit_type (type, res, overflowable, - (((sign == SIGNED || overflowable == -1) - && overflow) - | TREE_OVERFLOW (parg1) | TREE_OVERFLOW (parg2))); - - return t; + return true; } -/* Combine two integer constants PARG1 and PARG2 under operation CODE - to produce a new constant. Return NULL_TREE if we don't know how +/* Combine two poly int's ARG1 and ARG2 under operation CODE to + produce a new constant in RES. Return FALSE if we don't know how to evaluate CODE at compile-time. */ -static tree -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, - int overflowable) +static bool +poly_int_binop (poly_wide_int &res, enum tree_code code, + const_tree arg1, const_tree arg2, + signop sign, wi::overflow_type &overflow) { - if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) - return int_const_binop_2 (code, arg1, arg2, overflowable); - gcc_assert (NUM_POLY_INT_COEFFS != 1); - - if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + gcc_assert (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)); + switch (code) { - poly_wide_int res; - wi::overflow_type overflow; - tree type = TREE_TYPE (arg1); - signop sign = TYPE_SIGN (type); - switch (code) - { - case PLUS_EXPR: - res = wi::add (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case PLUS_EXPR: + res = wi::add (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MINUS_EXPR: - res = wi::sub (wi::to_poly_wide (arg1), - wi::to_poly_wide (arg2), sign, &overflow); - break; + case MINUS_EXPR: + res = wi::sub (wi::to_poly_wide (arg1), + wi::to_poly_wide (arg2), sign, &overflow); + break; - case MULT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg1), - wi::to_wide (arg2), sign, &overflow); - else if (TREE_CODE (arg1) == INTEGER_CST) - res = wi::mul (wi::to_poly_wide (arg2), - wi::to_wide (arg1), sign, &overflow); - else - return NULL_TREE; - break; + case MULT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg1), + wi::to_wide (arg2), sign, &overflow); + else if (TREE_CODE (arg1) == INTEGER_CST) + res = wi::mul (wi::to_poly_wide (arg2), + wi::to_wide (arg1), sign, &overflow); + else + return NULL_TREE; + break; - case LSHIFT_EXPR: - if (TREE_CODE (arg2) == INTEGER_CST) - res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); - else - return NULL_TREE; - break; + case LSHIFT_EXPR: + if (TREE_CODE (arg2) == INTEGER_CST) + res = wi::to_poly_wide (arg1) << wi::to_wide (arg2); + else + return false; + break; - case BIT_IOR_EXPR: - if (TREE_CODE (arg2) != INTEGER_CST - || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), - &res)) - return NULL_TREE; - break; + case BIT_IOR_EXPR: + if (TREE_CODE (arg2) != INTEGER_CST + || !can_ior_p (wi::to_poly_wide (arg1), wi::to_wide (arg2), + &res)) + return false; + break; - default: - return NULL_TREE; - } - return force_fit_type (type, res, overflowable, - (((sign == SIGNED || overflowable == -1) - && overflow) - | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); + default: + return false; } - - return NULL_TREE; + return true; } +/* Combine two integer constants ARG1 and ARG2 under operation CODE to + produce a new constant. Return NULL_TREE if we don't know how to + evaluate CODE at compile-time. */ + tree -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, + int overflowable) { - return int_const_binop_1 (code, arg1, arg2, 1); + bool success = false; + poly_wide_int poly_res; + tree type = TREE_TYPE (arg1); + signop sign = TYPE_SIGN (type); + wi::overflow_type overflow = wi::OVF_NONE; + + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) + { + wide_int warg1 = wi::to_wide (arg1), res; + wide_int warg2 = wi::to_wide (arg2, TYPE_PRECISION (type)); + success = wide_int_binop (res, code, warg1, warg2, sign, overflow); + poly_res = res; + } + else if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) + success = poly_int_binop (poly_res, code, arg1, arg2, sign, overflow); + if (success) + return force_fit_type (type, poly_res, overflowable, + (((sign == SIGNED || overflowable == -1) + && overflow) + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); + return NULL_TREE; } /* Return true if binary operation OP distributes over addition in operand @@ -1925,7 +1930,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) /* Handle general case of two integer constants. For sizetype constant calculations we always want to know about overflow, even in the unsigned case. */ - tree res = int_const_binop_1 (code, arg0, arg1, -1); + tree res = int_const_binop (code, arg0, arg1, -1); if (res != NULL_TREE) return res; } diff --git a/gcc/fold-const.h b/gcc/fold-const.h index 4613a62e1f6..cc80f4a7176 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, tree, enum tree_code, tree, tree, tree, enum tree_code, tree, tree, tree *); extern tree fold_read_from_constant_string (tree); -extern tree int_const_binop (enum tree_code, const_tree, const_tree); +extern bool wide_int_binop (wide_int &res, enum tree_code, + const wide_int &arg1, const wide_int &arg2, + signop, wi::overflow_type &); +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); #define build_fold_addr_expr(T)\ build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) extern tree build_fold_addr_expr_loc (location_t, tree); diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a7453abba7f..db0e8e1e142 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) return NULL_TREE; } -/* Wrapper around int_const_binop. Return true if we can compute the - result; i.e. if the operation doesn't overflow or if the overflow is - undefined. In the latter case (if the operation overflows and - overflow is undefined), then adjust the result to be -INF or +INF - depending on CODE, VAL1 and VAL2. Return the value in *RES. +/* Wrapper around wide_int_binop that adjusts for overflow. + + Return true if we can compute the result; i.e. if the operation + doesn't overflow or if the overflow is undefined. In the latter + case (if the operation overflows and overflow is undefined), then + adjust the result to be -INF or +INF depending on CODE, VAL1 and + VAL2. Return the value in *RES. Return false for division by zero, for which the result is indeterminate. */ @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) { wi::overflow_type overflow = wi::OVF_NONE; signop sign = TYPE_SIGN (TREE_TYPE (val1)); + wide_int w1 = wi::to_wide (val1); + wide_int w2 = wi::to_wide (val2); switch (code) { case RSHIFT_EXPR: case LSHIFT_EXPR: - { - wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); - if (wi::neg_p (wval2)) - { - wval2 = -wval2; - if (code == RSHIFT_EXPR) - code = LSHIFT_EXPR; - else - code = RSHIFT_EXPR; - } - - if (code == RSHIFT_EXPR) - /* It's unclear from the C standard whether shifts can overflow. - The following code ignores overflow; perhaps a C standard - interpretation ruling is needed. */ - *res = wi::rshift (wi::to_wide (val1), wval2, sign); - else - *res = wi::lshift (wi::to_wide (val1), wval2); - break; - } - + w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); + /* FALLTHRU */ case MULT_EXPR: - *res = wi::mul (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: - if (val2 == 0) - return false; - else - *res = wi::div_trunc (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case FLOOR_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_floor (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case CEIL_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_ceil (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case ROUND_DIV_EXPR: - if (val2 == 0) + if (!wide_int_binop (*res, code, w1, w2, sign, overflow)) return false; - *res = wi::div_round (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); break; default: gcc_unreachable (); } + /* If the operation overflowed return -INF or +INF depending on the + operation and the combination of signs of the operands. */ if (overflow && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) { - /* If the operation overflowed return -INF or +INF depending - on the operation and the combination of signs of the operands. */ - int sgn1 = tree_int_cst_sgn (val1); - int sgn2 = tree_int_cst_sgn (val2); + int sign1 = tree_int_cst_sgn (val1); + int sign2 = tree_int_cst_sgn (val2); /* Notice that we only need to handle the restricted set of operations handled by extract_range_from_binary_expr. @@ -1053,64 +1013,47 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) /* For multiplication, the sign of the overflow is given by the comparison of the signs of the operands. */ - if ((code == MULT_EXPR && sgn1 == sgn2) - /* For addition, the operands must be of the same sign - to yield an overflow. Its sign is therefore that - of one of the operands, for example the first. */ - || (code == PLUS_EXPR && sgn1 >= 0) - /* For subtraction, operands must be of - different signs to yield an overflow. Its sign is - therefore that of the first operand or the opposite of - that of the second operand. A first operand of 0 counts - as positive here, for the corner case 0 - (-INF), which - overflows, but must yield +INF. */ - || (code == MINUS_EXPR && sgn1 >= 0) + if ((code == MULT_EXPR && sign1 == sign2) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR || code == CEIL_DIV_EXPR || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) - *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); else - *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); return true; } return !overflow; } - -/* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO - bitmask if some bit is unset, it means for all numbers in the range +/* For range [LB, UB] compute two wide_int bitmasks. In *MAY_BE_NONZERO + bitmask, if some bit is unset, it means for all numbers in the range the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO - bitmask if some bit is set, it means for all numbers in the range + bitmask, if some bit is set, it means for all numbers in the range the bit is 1, otherwise it might be 0 or 1. */ -bool -zero_nonzero_bits_from_vr (const tree expr_type, - value_range *vr, - wide_int *may_be_nonzero, - wide_int *must_be_nonzero) +void +zero_nonzero_bits_from_bounds (signop sign, + const wide_int &lb, const wide_int &ub, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) { - *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); - *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); - if (!range_int_cst_p (vr)) - return false; + *may_be_nonzero = wi::minus_one (lb.get_precision ()); + *must_be_nonzero = wi::zero (lb.get_precision ()); - if (range_int_cst_singleton_p (vr)) + if (wi::eq_p (lb, ub)) { - *may_be_nonzero = wi::to_wide (vr->min); + *may_be_nonzero = lb; *must_be_nonzero = *may_be_nonzero; } - else if (tree_int_cst_sgn (vr->min) >= 0 - || tree_int_cst_sgn (vr->max) < 0) + else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) { - wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max); - *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max); - *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max); + wide_int xor_mask = lb ^ ub; + *may_be_nonzero = lb | ub; + *must_be_nonzero = lb & ub; if (xor_mask != 0) { wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, @@ -1119,7 +1062,26 @@ zero_nonzero_bits_from_vr (const tree expr_type, *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask); } } +} +/* Like zero_nonzero_bits_from_bounds, but use the range in value_range VR. */ + +bool +zero_nonzero_bits_from_vr (const tree expr_type, + value_range *vr, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) +{ + if (!range_int_cst_p (vr)) + { + *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); + *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); + return false; + } + + zero_nonzero_bits_from_bounds (TYPE_SIGN (expr_type), + wi::to_wide (vr->min), wi::to_wide (vr->max), + may_be_nonzero, must_be_nonzero); return true; } @@ -1275,6 +1237,52 @@ extract_range_from_multiplicative_op_1 (value_range *vr, wide_int_to_tree (type, max), NULL); } +/* For op & or | attempt to optimize: + + [LB, UB] op Z + into: + [LB op Z, UB op Z] + + if Z is a constant which (for op | its bitwise not) has n + consecutive least significant bits cleared followed by m 1 + consecutive bits set immediately above it and either + m + n == precision, or (x >> (m + n)) == (y >> (m + n)). + + The least significant n bits of all the values in the range are + cleared or set, the m bits above it are preserved and any bits + above these are required to be the same for all values in the + range. + + Return TRUE if the min and max can simply be folded. */ + +bool +range_easy_mask_min_max (tree_code code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask) + +{ + wide_int w = mask; + int m = 0, n = 0; + if (code == BIT_IOR_EXPR) + w = ~w; + if (wi::eq_p (w, 0)) + n = w.get_precision (); + else + { + n = wi::ctz (w); + w = ~(w | wi::mask (n, false, w.get_precision ())); + if (wi::eq_p (w, 0)) + m = w.get_precision () - n; + else + m = wi::ctz (w) - n; + } + wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); + if ((new_mask & lb) == (new_mask & ub)) + return true; + + return false; +} + /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -2175,39 +2183,14 @@ extract_range_from_binary_expr_1 (value_range *vr, vr1p = &vr0; } /* For op & or | attempt to optimize: - [x, y] op z into [x op z, y op z] - if z is a constant which (for op | its bitwise not) has n - consecutive least significant bits cleared followed by m 1 - consecutive bits set immediately above it and either - m + n == precision, or (x >> (m + n)) == (y >> (m + n)). - The least significant n bits of all the values in the range are - cleared or set, the m bits above it are preserved and any bits - above these are required to be the same for all values in the - range. */ - if (vr0p && range_int_cst_p (vr0p)) + [x, y] op z into [x op z, y op z]. */ + if (vr0p && range_int_cst_p (vr0p) + && range_easy_mask_min_max (code, wi::to_wide (vr0p->min), + wi::to_wide (vr0p->max), + wi::to_wide (vr1p->min))) { - wide_int w = wi::to_wide (vr1p->min); - int m = 0, n = 0; - if (code == BIT_IOR_EXPR) - w = ~w; - if (wi::eq_p (w, 0)) - n = TYPE_PRECISION (expr_type); - else - { - n = wi::ctz (w); - w = ~(w | wi::mask (n, false, w.get_precision ())); - if (wi::eq_p (w, 0)) - m = TYPE_PRECISION (expr_type) - n; - else - m = wi::ctz (w) - n; - } - wide_int mask = wi::mask (m + n, true, w.get_precision ()); - if ((mask & wi::to_wide (vr0p->min)) - == (mask & wi::to_wide (vr0p->max))) - { - min = int_const_binop (code, vr0p->min, vr1p->min); - max = int_const_binop (code, vr0p->max, vr1p->min); - } + min = int_const_binop (code, vr0p->min, vr1p->min); + max = int_const_binop (code, vr0p->max, vr1p->min); } } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 608ca5658b5..946e26e29b4 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -112,8 +112,14 @@ extern bool range_int_cst_p (value_range *); extern int operand_less_p (tree, tree); extern bool find_case_label_range (gswitch *, tree, tree, size_t *, size_t *); extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); +extern void zero_nonzero_bits_from_bounds (signop, const wide_int&, + const wide_int&, wide_int *, + wide_int *); extern bool zero_nonzero_bits_from_vr (const tree, value_range *, wide_int *, wide_int *); +extern bool range_easy_mask_min_max (tree_code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask); extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); extern bool range_int_cst_singleton_p (value_range *); extern int value_inside_range (tree, tree, tree);
Aldy Hernandez <aldyh@redhat.com> writes: > On 07/11/2018 01:33 PM, Richard Sandiford wrote: >> Aldy Hernandez <aldyh@redhat.com> writes: >>> On 07/11/2018 08:52 AM, Richard Biener wrote: >>>> On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >>>>> >>>>> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >>>>> I don't think anyone will mind the adjustment to the patch ;-). >>>>> >>>>> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >>>>> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >>>>> and then use a default argument for int_const_binop() to get things going. >>>>> >>>>> Sorry for more changes in flight, but I thought we could benefit from >>>>> more cleanups :). >>>>> >>>>> OK for trunk pending tests? >>>> >>>> Much of GCC pre-dates function overloading / default args ;) >>> >>> Heh...and ANSI C. >>> >>>> >>>> Looks OK but can you please rename your tree_binop to int_cst_binop? >>>> Or maybe inline it into int_const_binop, also sharing the force_fit_type () >>>> tail with poly_int_binop? >>> >>> I tried both, but inlining looked cleaner :). Done. >>> >>>> >>>> What about mixed INTEGER_CST / poly_int constants? Shouldn't it >>>> be >>>> >>>> if (neither-poly-nor-integer-cst (arg1 || arg2)) >>>> return NULL_TREE; >>>> if (poly_int_tree (arg1) || poly_int_tree (arg2)) >>>> poly-int-stuff >>>> else if (INTEGER_CST && INTEGER_CST) >>>> wide-int-stuff >>>> >>>> ? I see that is a pre-existing issue but if you are at refactoring... >>>> wi::to_poly_wide should handle INTEGER_CST operands just fine >>>> I hope. >>> >>> This aborted: >>> gcc_assert (NUM_POLY_INT_COEFFS != 1); >>> >>> but even taking it out made the bootstrap die somewhere else. >>> >>> If it's ok, I'd rather not tackle this now, as I have some more cleanups >>> that are pending on this. If you feel strongly, I could do it at a >>> later time. >>> >>> OK pending tests? >> >> LGTM FWIW, just some nits: >> >>> -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ >>> +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce >>> + a new constant in RES. Return FALSE if we don't know how to >>> + evaluate CODE at compile-time. */ >>> >>> -static tree >>> -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, >>> - int overflowable) >>> +bool >>> +wide_int_binop (enum tree_code code, >>> + wide_int &res, const wide_int &arg1, const wide_int &arg2, >>> + signop sign, wi::overflow_type &overflow) >>> { >> >> IMO we should avoid pass-back by reference like the plague. :-) >> It's especially confusing when the code does things like: >> >> case FLOOR_DIV_EXPR: >> if (arg2 == 0) >> return false; >> res = wi::div_floor (arg1, arg2, sign, &overflow); >> break; > > > > It looked at first like it was taking the address of a local variable > > and failing to propagate the information back up. > > > > I think we should stick to using pointers for this kind of thing. > > > > Hmmm, I kinda like them. It just takes some getting used to, but > generally yields cleaner code as you don't have to keep using '*' > everywhere. Plus, the callee can assume the pointer is non-zero. But it can assume that for "*" too. The problem isn't getting used to them. I've worked on codebases where this is the norm before and had to live with it. It's just always felt a mistake even then. E.g. compare: int_const_binop_1 (code, arg1, arg2, overflowable); and: wide_int_binop (code, res, arg1, arg2, sign, overflow); There's just no visual clue to tell you that "overflowable" is an input and "overflow" is an output. ("overflowable" could well be an output from the raw meaning: "the calculation might have induced an overflow, but we're not sure".) I wouldn't mind so much if we had a convention that the outputs had a suffix to make it clear that they were outputs. But that would be more typing than "*". Thanks, Richard
On 07/12/2018 04:29 AM, Richard Sandiford wrote: > Aldy Hernandez <aldyh@redhat.com> writes: >> On 07/11/2018 01:33 PM, Richard Sandiford wrote: >>> Aldy Hernandez <aldyh@redhat.com> writes: >>>> On 07/11/2018 08:52 AM, Richard Biener wrote: >>>>> On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: >>>>>> >>>>>> Hmmm, I think we can do better, and since this hasn't been reviewed yet, >>>>>> I don't think anyone will mind the adjustment to the patch ;-). >>>>>> >>>>>> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract >>>>>> them into properly named poly_int_binop, wide_int_binop, and tree_binop, >>>>>> and then use a default argument for int_const_binop() to get things going. >>>>>> >>>>>> Sorry for more changes in flight, but I thought we could benefit from >>>>>> more cleanups :). >>>>>> >>>>>> OK for trunk pending tests? >>>>> >>>>> Much of GCC pre-dates function overloading / default args ;) >>>> >>>> Heh...and ANSI C. >>>> >>>>> >>>>> Looks OK but can you please rename your tree_binop to int_cst_binop? >>>>> Or maybe inline it into int_const_binop, also sharing the force_fit_type () >>>>> tail with poly_int_binop? >>>> >>>> I tried both, but inlining looked cleaner :). Done. >>>> >>>>> >>>>> What about mixed INTEGER_CST / poly_int constants? Shouldn't it >>>>> be >>>>> >>>>> if (neither-poly-nor-integer-cst (arg1 || arg2)) >>>>> return NULL_TREE; >>>>> if (poly_int_tree (arg1) || poly_int_tree (arg2)) >>>>> poly-int-stuff >>>>> else if (INTEGER_CST && INTEGER_CST) >>>>> wide-int-stuff >>>>> >>>>> ? I see that is a pre-existing issue but if you are at refactoring... >>>>> wi::to_poly_wide should handle INTEGER_CST operands just fine >>>>> I hope. >>>> >>>> This aborted: >>>> gcc_assert (NUM_POLY_INT_COEFFS != 1); >>>> >>>> but even taking it out made the bootstrap die somewhere else. >>>> >>>> If it's ok, I'd rather not tackle this now, as I have some more cleanups >>>> that are pending on this. If you feel strongly, I could do it at a >>>> later time. >>>> >>>> OK pending tests? >>> >>> LGTM FWIW, just some nits: >>> >>>> -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ >>>> +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce >>>> + a new constant in RES. Return FALSE if we don't know how to >>>> + evaluate CODE at compile-time. */ >>>> >>>> -static tree >>>> -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, >>>> - int overflowable) >>>> +bool >>>> +wide_int_binop (enum tree_code code, >>>> + wide_int &res, const wide_int &arg1, const wide_int &arg2, >>>> + signop sign, wi::overflow_type &overflow) >>>> { >>> >>> IMO we should avoid pass-back by reference like the plague. :-) >>> It's especially confusing when the code does things like: >>> >>> case FLOOR_DIV_EXPR: >>> if (arg2 == 0) >>> return false; >>> res = wi::div_floor (arg1, arg2, sign, &overflow); >>> break; >> > >> > It looked at first like it was taking the address of a local variable >> > and failing to propagate the information back up. >> > >> > I think we should stick to using pointers for this kind of thing. >> > >> >> Hmmm, I kinda like them. It just takes some getting used to, but >> generally yields cleaner code as you don't have to keep using '*' >> everywhere. Plus, the callee can assume the pointer is non-zero. > > But it can assume that for "*" too. > > The problem isn't getting used to them. I've worked on codebases where > this is the norm before and had to live with it. It's just always felt > a mistake even then. > > E.g. compare: > > int_const_binop_1 (code, arg1, arg2, overflowable); > > and: > > wide_int_binop (code, res, arg1, arg2, sign, overflow); > > There's just no visual clue to tell you that "overflowable" is an > input and "overflow" is an output. ("overflowable" could well be > an output from the raw meaning: "the calculation might have induced > an overflow, but we're not sure".) > > I wouldn't mind so much if we had a convention that the outputs > had a suffix to make it clear that they were outputs. But that > would be more typing than "*". Perhaps a proposal for the coding conventions document? ;-) Aldy
On Thu, Jul 12, 2018 at 10:12 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > On 07/11/2018 01:33 PM, Richard Sandiford wrote: > > Aldy Hernandez <aldyh@redhat.com> writes: > >> On 07/11/2018 08:52 AM, Richard Biener wrote: > >>> On Wed, Jul 11, 2018 at 8:48 AM Aldy Hernandez <aldyh@redhat.com> wrote: > >>>> > >>>> Hmmm, I think we can do better, and since this hasn't been reviewed yet, > >>>> I don't think anyone will mind the adjustment to the patch ;-). > >>>> > >>>> I really hate int_const_binop_SOME_RANDOM_NUMBER. We should abstract > >>>> them into properly named poly_int_binop, wide_int_binop, and tree_binop, > >>>> and then use a default argument for int_const_binop() to get things going. > >>>> > >>>> Sorry for more changes in flight, but I thought we could benefit from > >>>> more cleanups :). > >>>> > >>>> OK for trunk pending tests? > >>> > >>> Much of GCC pre-dates function overloading / default args ;) > >> > >> Heh...and ANSI C. > >> > >>> > >>> Looks OK but can you please rename your tree_binop to int_cst_binop? > >>> Or maybe inline it into int_const_binop, also sharing the force_fit_type () > >>> tail with poly_int_binop? > >> > >> I tried both, but inlining looked cleaner :). Done. > >> > >>> > >>> What about mixed INTEGER_CST / poly_int constants? Shouldn't it > >>> be > >>> > >>> if (neither-poly-nor-integer-cst (arg1 || arg2)) > >>> return NULL_TREE; > >>> if (poly_int_tree (arg1) || poly_int_tree (arg2)) > >>> poly-int-stuff > >>> else if (INTEGER_CST && INTEGER_CST) > >>> wide-int-stuff > >>> > >>> ? I see that is a pre-existing issue but if you are at refactoring... > >>> wi::to_poly_wide should handle INTEGER_CST operands just fine > >>> I hope. > >> > >> This aborted: > >> gcc_assert (NUM_POLY_INT_COEFFS != 1); > >> > >> but even taking it out made the bootstrap die somewhere else. > >> > >> If it's ok, I'd rather not tackle this now, as I have some more cleanups > >> that are pending on this. If you feel strongly, I could do it at a > >> later time. > >> > >> OK pending tests? > > > > LGTM FWIW, just some nits: > > > >> -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ > >> +/* Combine two wide ints ARG1 and ARG2 under operation CODE to produce > >> + a new constant in RES. Return FALSE if we don't know how to > >> + evaluate CODE at compile-time. */ > >> > >> -static tree > >> -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, > >> - int overflowable) > >> +bool > >> +wide_int_binop (enum tree_code code, > >> + wide_int &res, const wide_int &arg1, const wide_int &arg2, > >> + signop sign, wi::overflow_type &overflow) > >> { > > > > IMO we should avoid pass-back by reference like the plague. :-) > > It's especially confusing when the code does things like: > > > > case FLOOR_DIV_EXPR: > > if (arg2 == 0) > > return false; > > res = wi::div_floor (arg1, arg2, sign, &overflow); > > break; > > > > It looked at first like it was taking the address of a local variable > > and failing to propagate the information back up. > > > > I think we should stick to using pointers for this kind of thing. > > > > Hmmm, I kinda like them. It just takes some getting used to, but > generally yields cleaner code as you don't have to keep using '*' > everywhere. Plus, the callee can assume the pointer is non-zero. > > >> -/* Combine two integer constants PARG1 and PARG2 under operation CODE > >> - to produce a new constant. Return NULL_TREE if we don't know how > >> +/* Combine two poly int's ARG1 and ARG2 under operation CODE to > >> + produce a new constant in RES. Return FALSE if we don't know how > >> to evaluate CODE at compile-time. */ > >> > >> -static tree > >> -int_const_binop_1 (enum tree_code code, const_tree arg1, const_tree arg2, > >> - int overflowable) > >> +static bool > >> +poly_int_binop (poly_wide_int &res, enum tree_code code, > >> + const_tree arg1, const_tree arg2, > >> + signop sign, wi::overflow_type &overflow) > >> { > > > > Would be good to be consistent about the order of the result and code > > arguments. Here it's "result, code" (which seems better IMO), > > but in wide_int_binop it's "code, result". > > Agreed. Fixed. > > > > >> +/* Combine two integer constants PARG1 and PARG2 under operation CODE > >> + to produce a new constant. Return NULL_TREE if we don't know how > >> + to evaluate CODE at compile-time. */ > >> + > >> tree > >> -int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2) > >> +int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2, > >> + int overflowable) > > > > s/PARG/ARG/g in comment. > > Fixed. > > > > >> { > >> - return int_const_binop_1 (code, arg1, arg2, 1); > >> + bool success = false; > >> + poly_wide_int poly_res; > >> + tree type = TREE_TYPE (arg1); > >> + signop sign = TYPE_SIGN (type); > >> + wi::overflow_type overflow = wi::OVF_NONE; > >> + > >> + if (TREE_CODE (arg1) == INTEGER_CST && TREE_CODE (arg2) == INTEGER_CST) > >> + { > >> + wide_int warg1 = wi::to_wide (arg1), res; > >> + wide_int warg2 = wi::to_wide (arg2, TYPE_PRECISION (type)); > >> + success = wide_int_binop (code, res, warg1, warg2, sign, overflow); > >> + poly_res = res; > >> + } > >> + else if (poly_int_tree_p (arg1) && poly_int_tree_p (arg2)) > >> + success = poly_int_binop (poly_res, code, arg1, arg2, sign, overflow); > >> + if (success) > >> + return force_fit_type (type, poly_res, overflowable, > >> + (((sign == SIGNED || overflowable == -1) > >> + && overflow) > >> + | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))); > >> + return NULL_TREE; > >> } > >> > >> /* Return true if binary operation OP distributes over addition in operand > >> @@ -1925,7 +1930,7 @@ size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1) > >> /* Handle general case of two integer constants. For sizetype > >> constant calculations we always want to know about overflow, > >> even in the unsigned case. */ > >> - tree res = int_const_binop_1 (code, arg0, arg1, -1); > >> + tree res = int_const_binop (code, arg0, arg1, -1); > >> if (res != NULL_TREE) > >> return res; > >> } > >> diff --git a/gcc/fold-const.h b/gcc/fold-const.h > >> index 4613a62e1f6..b921ba86854 100644 > >> --- a/gcc/fold-const.h > >> +++ b/gcc/fold-const.h > >> @@ -100,7 +100,10 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, > >> tree, enum tree_code, tree, tree, > >> tree, enum tree_code, tree, tree, tree *); > >> extern tree fold_read_from_constant_string (tree); > >> -extern tree int_const_binop (enum tree_code, const_tree, const_tree); > >> +extern bool wide_int_binop (enum tree_code, wide_int &res, > >> + const wide_int &arg1, const wide_int &arg2, > >> + signop, wi::overflow_type &); > >> +extern tree int_const_binop (enum tree_code, const_tree, const_tree, int = 1); > >> #define build_fold_addr_expr(T)\ > >> build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) > >> extern tree build_fold_addr_expr_loc (location_t, tree); > >> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > >> index a7453abba7f..7764f7b30b6 100644 > >> --- a/gcc/tree-vrp.c > >> +++ b/gcc/tree-vrp.c > >> @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) > >> return NULL_TREE; > >> } > >> > >> -/* Wrapper around int_const_binop. Return true if we can compute the > >> - result; i.e. if the operation doesn't overflow or if the overflow is > >> - undefined. In the latter case (if the operation overflows and > >> - overflow is undefined), then adjust the result to be -INF or +INF > >> - depending on CODE, VAL1 and VAL2. Return the value in *RES. > >> +/* Wrapper around wide_int_binop that adjusts for overflow. > >> + > >> + Return true if we can compute the result; i.e. if the operation > >> + doesn't overflow or if the overflow is undefined. In the latter > >> + case (if the operation overflows and overflow is undefined), then > >> + adjust the result to be -INF or +INF depending on CODE, VAL1 and > >> + VAL2. Return the value in *RES. > >> > >> Return false for division by zero, for which the result is > >> indeterminate. */ > >> @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) > >> { > >> wi::overflow_type overflow = wi::OVF_NONE; > >> signop sign = TYPE_SIGN (TREE_TYPE (val1)); > >> + wide_int w1 = wi::to_wide (val1); > >> + wide_int w2 = wi::to_wide (val2); > >> > > > > This doesn't come for free. Until we can use "auto", it might be better > > to keep the wi::to_wide calls at the point they're used. That probably > > maans having a separate call to wide_int_binop for shifts. > > I would prefer cleaner rather than saving a few microseconds or bytes, > unless it's in the critical path. This particular code doesn't seem to > be ??. So besides the general discussion about references/pointers for out parameters let's stay consistet within related APIs. This means wide_int_binop should have a wide_int wide_int_binop (enum tree_code, const wide_int &, const wide_int &, signop, wi::overflow_type *) signature. Notice how I elided the out wide_int parameter to be the return value which means the function isn't supposed to fail which means gcc_unreachable () for "unhandled" tree codes. It's more like an exceptional state anyway. The same goes for the poly_int_binop signature. The already existing wi::accumulate_overflow should probably be re-done as wi::overflow_type wi::accumulate_overflow (wi::overflow_type, wi::overflow_type); Richard. > Thanks for the review! > Aldy
On 07/13/2018 03:02 AM, Richard Biener wrote: > On Thu, Jul 12, 2018 at 10:12 AM Aldy Hernandez <aldyh@redhat.com> wrote: > So besides the general discussion about references/pointers for out parameters > let's stay consistet within related APIs. This means wide_int_binop should > have a > > wide_int > wide_int_binop (enum tree_code, const wide_int &, const wide_int &, > signop, wi::overflow_type *) > > signature. Notice how I elided the out wide_int parameter to be the > return value which means > the function isn't supposed to fail which means gcc_unreachable () for > "unhandled" tree codes. wide_int_binop was returning failure for: > case CEIL_DIV_EXPR: > if (arg2 == 0) > return false; > res = wi::div_ceil (arg1, arg2, sign, &overflow); > break; > > case ROUND_DIV_EXPR: > if (arg2 == 0) > return false; > res = wi::div_round (arg1, arg2, sign, &overflow); > break; etc How do you suggest we indicate success/failure to the caller? Aldy > It's more like an exceptional state anyway. > > The same goes for the poly_int_binop signature. > > The already existing wi::accumulate_overflow should probably be re-done as > > wi::overflow_type wi::accumulate_overflow (wi::overflow_type, > wi::overflow_type); > > Richard. > >> Thanks for the review! >> Aldy
On Fri, Jul 13, 2018 at 10:05 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > On 07/13/2018 03:02 AM, Richard Biener wrote: > > On Thu, Jul 12, 2018 at 10:12 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > So besides the general discussion about references/pointers for out parameters > > let's stay consistet within related APIs. This means wide_int_binop should > > have a > > > > wide_int > > wide_int_binop (enum tree_code, const wide_int &, const wide_int &, > > signop, wi::overflow_type *) > > > > signature. Notice how I elided the out wide_int parameter to be the > > return value which means > > the function isn't supposed to fail which means gcc_unreachable () for > > "unhandled" tree codes. > > wide_int_binop was returning failure for: > > > case CEIL_DIV_EXPR: > > if (arg2 == 0) > > return false; > > res = wi::div_ceil (arg1, arg2, sign, &overflow); > > break; > > > > case ROUND_DIV_EXPR: > > if (arg2 == 0) > > return false; > > res = wi::div_round (arg1, arg2, sign, &overflow); > > break; > etc > > How do you suggest we indicate success/failure to the caller? Oh, ok. Exceptions? (eh...) Well, so I guess you can leave the signature as-is apart from turing the overflow result into a pointer. OK with that change. Richard. > Aldy > > > It's more like an exceptional state anyway. > > > > The same goes for the poly_int_binop signature. > > > > The already existing wi::accumulate_overflow should probably be re-done as > > > > wi::overflow_type wi::accumulate_overflow (wi::overflow_type, > > wi::overflow_type); > > > > Richard. > > > >> Thanks for the review! > >> Aldy
On Fri, Jul 13, 2018 at 3:18 PM Richard Biener <richard.guenther@gmail.com> wrote: > > On Fri, Jul 13, 2018 at 10:05 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > > > On 07/13/2018 03:02 AM, Richard Biener wrote: > > > On Thu, Jul 12, 2018 at 10:12 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > So besides the general discussion about references/pointers for out parameters > > > let's stay consistet within related APIs. This means wide_int_binop should > > > have a > > > > > > wide_int > > > wide_int_binop (enum tree_code, const wide_int &, const wide_int &, > > > signop, wi::overflow_type *) > > > > > > signature. Notice how I elided the out wide_int parameter to be the > > > return value which means > > > the function isn't supposed to fail which means gcc_unreachable () for > > > "unhandled" tree codes. > > > > wide_int_binop was returning failure for: > > > > > case CEIL_DIV_EXPR: > > > if (arg2 == 0) > > > return false; > > > res = wi::div_ceil (arg1, arg2, sign, &overflow); > > > break; > > > > > > case ROUND_DIV_EXPR: > > > if (arg2 == 0) > > > return false; > > > res = wi::div_round (arg1, arg2, sign, &overflow); > > > break; > > etc > > > > How do you suggest we indicate success/failure to the caller? > > Oh, ok. Exceptions? (eh...) > > Well, so I guess you can leave the signature as-is apart from turing > the overflow > result into a pointer. Alternatively handle it like wi::sdiv and friends which indicate overflow and use a zero result. Thus, remove the "failure" path here. Of course when used via the tree interface this probably isn't the desired result which means this really isn't a general wide-int op with code thing but only a helper for int_cst_binop :/ So alternatively do the interface I suggested w/o the zero checks and do the zero checks in the int_const_binop caller. Richard. > OK with that change. > Richard. > > > Aldy > > > > > It's more like an exceptional state anyway. > > > > > > The same goes for the poly_int_binop signature. > > > > > > The already existing wi::accumulate_overflow should probably be re-done as > > > > > > wi::overflow_type wi::accumulate_overflow (wi::overflow_type, > > > wi::overflow_type); > > > > > > Richard. > > > > > >> Thanks for the review! > > >> Aldy
gcc/ * fold-const.c (int_const_binop_2): Abstract wide int code to... (wide_int_binop): ...here. * fold-const.h (wide_int_binop): New. * tree-vrp.c (vrp_int_const_binop): Call wide_int_binop. Remove useless PLUS/MINUS_EXPR case. (zero_nonzero_bits_from_vr): Move wide int code... (zero_nonzero_bits_from_bounds): ...here. (extract_range_from_binary_expr_1): Move mask optimization code... (range_easy_mask_min_max): ...here. * tree-vrp.h (zero_nonzero_bits_from_bounds): New. (range_easy_mask_min_max): New. diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 5b94c700c81..35171c5de08 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -966,21 +966,18 @@ int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2 && TYPE_MODE (type1) == TYPE_MODE (type2); } -/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ - -static tree -int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, - int overflowable) -{ - wide_int res; - tree t; - tree type = TREE_TYPE (parg1); - signop sign = TYPE_SIGN (type); - wi::overflow_type overflow = wi::OVF_NONE; +/* Perform binary tree operation CODE on ARG1 and ARG2 and return the + result in RES. If an overflow occurs, it is stored in OVERFLOW. - wi::tree_to_wide_ref arg1 = wi::to_wide (parg1); - wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); + Return TRUE if the operation is handled and was successful. */ +bool +wide_int_binop (enum tree_code code, + wide_int &res, const wide_int &arg1, const wide_int &arg2, + signop sign, wi::overflow_type &overflow) +{ + wide_int tmp; + overflow = wi::OVF_NONE; switch (code) { case BIT_IOR_EXPR: @@ -999,37 +996,41 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case LSHIFT_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RSHIFT_EXPR) code = LSHIFT_EXPR; else code = RSHIFT_EXPR; } + else + tmp = arg2; if (code == RSHIFT_EXPR) /* It's unclear from the C standard whether shifts can overflow. The following code ignores overflow; perhaps a C standard interpretation ruling is needed. */ - res = wi::rshift (arg1, arg2, sign); + res = wi::rshift (arg1, tmp, sign); else - res = wi::lshift (arg1, arg2); + res = wi::lshift (arg1, tmp); break; case RROTATE_EXPR: case LROTATE_EXPR: if (wi::neg_p (arg2)) { - arg2 = -arg2; + tmp = -arg2; if (code == RROTATE_EXPR) code = LROTATE_EXPR; else code = RROTATE_EXPR; } + else + tmp = arg2; if (code == RROTATE_EXPR) - res = wi::rrotate (arg1, arg2); + res = wi::rrotate (arg1, tmp); else - res = wi::lrotate (arg1, arg2); + res = wi::lrotate (arg1, tmp); break; case PLUS_EXPR: @@ -1051,49 +1052,49 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_floor (arg1, arg2, sign, &overflow); break; case CEIL_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_ceil (arg1, arg2, sign, &overflow); break; case ROUND_DIV_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::div_round (arg1, arg2, sign, &overflow); break; case TRUNC_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_trunc (arg1, arg2, sign, &overflow); break; case FLOOR_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_floor (arg1, arg2, sign, &overflow); break; case CEIL_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_ceil (arg1, arg2, sign, &overflow); break; case ROUND_MOD_EXPR: if (arg2 == 0) - return NULL_TREE; + return false; res = wi::mod_round (arg1, arg2, sign, &overflow); break; @@ -1106,8 +1107,29 @@ int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, break; default: - return NULL_TREE; + return false; } + return true; +} + +/* Subroutine of int_const_binop_1 that handles two INTEGER_CSTs. */ + + +static tree +int_const_binop_2 (enum tree_code code, const_tree parg1, const_tree parg2, + int overflowable) +{ + wide_int res; + tree t; + tree type = TREE_TYPE (parg1); + signop sign = TYPE_SIGN (type); + wi::overflow_type overflow = wi::OVF_NONE; + + wide_int arg1 = wi::to_wide (parg1); + wide_int arg2 = wi::to_wide (parg2, TYPE_PRECISION (type)); + + if (!wide_int_binop (code, res, arg1, arg2, sign, overflow)) + return NULL_TREE; t = force_fit_type (type, res, overflowable, (((sign == SIGNED || overflowable == -1) diff --git a/gcc/fold-const.h b/gcc/fold-const.h index c64b8d0ecf7..354e84a8e5b 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -100,6 +100,9 @@ extern tree fold_bit_and_mask (tree, tree, enum tree_code, tree, enum tree_code, tree, tree, tree, enum tree_code, tree, tree, tree *); extern tree fold_read_from_constant_string (tree); +extern bool wide_int_binop (enum tree_code, wide_int &res, + const wide_int &arg1, const wide_int &arg2, + signop, wi::overflow_type &); extern tree int_const_binop (enum tree_code, const_tree, const_tree); #define build_fold_addr_expr(T)\ build_fold_addr_expr_loc (UNKNOWN_LOCATION, (T)) diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index a7453abba7f..7764f7b30b6 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -956,11 +956,13 @@ value_range_constant_singleton (value_range *vr) return NULL_TREE; } -/* Wrapper around int_const_binop. Return true if we can compute the - result; i.e. if the operation doesn't overflow or if the overflow is - undefined. In the latter case (if the operation overflows and - overflow is undefined), then adjust the result to be -INF or +INF - depending on CODE, VAL1 and VAL2. Return the value in *RES. +/* Wrapper around wide_int_binop that adjusts for overflow. + + Return true if we can compute the result; i.e. if the operation + doesn't overflow or if the overflow is undefined. In the latter + case (if the operation overflows and overflow is undefined), then + adjust the result to be -INF or +INF depending on CODE, VAL1 and + VAL2. Return the value in *RES. Return false for division by zero, for which the result is indeterminate. */ @@ -970,78 +972,36 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) { wi::overflow_type overflow = wi::OVF_NONE; signop sign = TYPE_SIGN (TREE_TYPE (val1)); + wide_int w1 = wi::to_wide (val1); + wide_int w2 = wi::to_wide (val2); switch (code) { case RSHIFT_EXPR: case LSHIFT_EXPR: - { - wide_int wval2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); - if (wi::neg_p (wval2)) - { - wval2 = -wval2; - if (code == RSHIFT_EXPR) - code = LSHIFT_EXPR; - else - code = RSHIFT_EXPR; - } - - if (code == RSHIFT_EXPR) - /* It's unclear from the C standard whether shifts can overflow. - The following code ignores overflow; perhaps a C standard - interpretation ruling is needed. */ - *res = wi::rshift (wi::to_wide (val1), wval2, sign); - else - *res = wi::lshift (wi::to_wide (val1), wval2); - break; - } - + w2 = wi::to_wide (val2, TYPE_PRECISION (TREE_TYPE (val1))); + /* FALLTHRU */ case MULT_EXPR: - *res = wi::mul (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case TRUNC_DIV_EXPR: case EXACT_DIV_EXPR: - if (val2 == 0) - return false; - else - *res = wi::div_trunc (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case FLOOR_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_floor (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case CEIL_DIV_EXPR: - if (val2 == 0) - return false; - *res = wi::div_ceil (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); - break; - case ROUND_DIV_EXPR: - if (val2 == 0) + if (!wide_int_binop (code, *res, w1, w2, sign, overflow)) return false; - *res = wi::div_round (wi::to_wide (val1), - wi::to_wide (val2), sign, &overflow); break; default: gcc_unreachable (); } + /* If the operation overflowed return -INF or +INF depending on the + operation and the combination of signs of the operands. */ if (overflow && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) { - /* If the operation overflowed return -INF or +INF depending - on the operation and the combination of signs of the operands. */ - int sgn1 = tree_int_cst_sgn (val1); - int sgn2 = tree_int_cst_sgn (val2); + int sign1 = tree_int_cst_sgn (val1); + int sign2 = tree_int_cst_sgn (val2); /* Notice that we only need to handle the restricted set of operations handled by extract_range_from_binary_expr. @@ -1053,64 +1013,47 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2, wide_int *res) /* For multiplication, the sign of the overflow is given by the comparison of the signs of the operands. */ - if ((code == MULT_EXPR && sgn1 == sgn2) - /* For addition, the operands must be of the same sign - to yield an overflow. Its sign is therefore that - of one of the operands, for example the first. */ - || (code == PLUS_EXPR && sgn1 >= 0) - /* For subtraction, operands must be of - different signs to yield an overflow. Its sign is - therefore that of the first operand or the opposite of - that of the second operand. A first operand of 0 counts - as positive here, for the corner case 0 - (-INF), which - overflows, but must yield +INF. */ - || (code == MINUS_EXPR && sgn1 >= 0) + if ((code == MULT_EXPR && sign1 == sign2) /* For division, the only case is -INF / -1 = +INF. */ || code == TRUNC_DIV_EXPR || code == FLOOR_DIV_EXPR || code == CEIL_DIV_EXPR || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) - *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::max_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); else - *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), - TYPE_SIGN (TREE_TYPE (val1))); + *res = wi::min_value (TYPE_PRECISION (TREE_TYPE (val1)), sign); return true; } return !overflow; } - -/* For range VR compute two wide_int bitmasks. In *MAY_BE_NONZERO - bitmask if some bit is unset, it means for all numbers in the range +/* For range [LB, UB] compute two wide_int bitmasks. In *MAY_BE_NONZERO + bitmask, if some bit is unset, it means for all numbers in the range the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO - bitmask if some bit is set, it means for all numbers in the range + bitmask, if some bit is set, it means for all numbers in the range the bit is 1, otherwise it might be 0 or 1. */ -bool -zero_nonzero_bits_from_vr (const tree expr_type, - value_range *vr, - wide_int *may_be_nonzero, - wide_int *must_be_nonzero) +void +zero_nonzero_bits_from_bounds (signop sign, + const wide_int &lb, const wide_int &ub, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) { - *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); - *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); - if (!range_int_cst_p (vr)) - return false; + *may_be_nonzero = wi::minus_one (lb.get_precision ()); + *must_be_nonzero = wi::zero (lb.get_precision ()); - if (range_int_cst_singleton_p (vr)) + if (wi::eq_p (lb, ub)) { - *may_be_nonzero = wi::to_wide (vr->min); + *may_be_nonzero = lb; *must_be_nonzero = *may_be_nonzero; } - else if (tree_int_cst_sgn (vr->min) >= 0 - || tree_int_cst_sgn (vr->max) < 0) + else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) { - wide_int xor_mask = wi::to_wide (vr->min) ^ wi::to_wide (vr->max); - *may_be_nonzero = wi::to_wide (vr->min) | wi::to_wide (vr->max); - *must_be_nonzero = wi::to_wide (vr->min) & wi::to_wide (vr->max); + wide_int xor_mask = lb ^ ub; + *may_be_nonzero = lb | ub; + *must_be_nonzero = lb & ub; if (xor_mask != 0) { wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, @@ -1119,7 +1062,26 @@ zero_nonzero_bits_from_vr (const tree expr_type, *must_be_nonzero = wi::bit_and_not (*must_be_nonzero, mask); } } +} +/* Like zero_nonzero_bits_from_bounds, but use the range in value_range VR. */ + +bool +zero_nonzero_bits_from_vr (const tree expr_type, + value_range *vr, + wide_int *may_be_nonzero, + wide_int *must_be_nonzero) +{ + if (!range_int_cst_p (vr)) + { + *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type)); + *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type)); + return false; + } + + zero_nonzero_bits_from_bounds (TYPE_SIGN (expr_type), + wi::to_wide (vr->min), wi::to_wide (vr->max), + may_be_nonzero, must_be_nonzero); return true; } @@ -1275,6 +1237,52 @@ extract_range_from_multiplicative_op_1 (value_range *vr, wide_int_to_tree (type, max), NULL); } +/* For op & or | attempt to optimize: + + [LB, UB] op Z + into: + [LB op Z, UB op Z] + + if Z is a constant which (for op | its bitwise not) has n + consecutive least significant bits cleared followed by m 1 + consecutive bits set immediately above it and either + m + n == precision, or (x >> (m + n)) == (y >> (m + n)). + + The least significant n bits of all the values in the range are + cleared or set, the m bits above it are preserved and any bits + above these are required to be the same for all values in the + range. + + Return TRUE if the min and max can simply be folded. */ + +bool +range_easy_mask_min_max (tree_code code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask) + +{ + wide_int w = mask; + int m = 0, n = 0; + if (code == BIT_IOR_EXPR) + w = ~w; + if (wi::eq_p (w, 0)) + n = w.get_precision (); + else + { + n = wi::ctz (w); + w = ~(w | wi::mask (n, false, w.get_precision ())); + if (wi::eq_p (w, 0)) + m = w.get_precision () - n; + else + m = wi::ctz (w) - n; + } + wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); + if ((new_mask & lb) == (new_mask & ub)) + return true; + + return false; +} + /* If BOUND will include a symbolic bound, adjust it accordingly, otherwise leave it as is. @@ -2175,39 +2183,14 @@ extract_range_from_binary_expr_1 (value_range *vr, vr1p = &vr0; } /* For op & or | attempt to optimize: - [x, y] op z into [x op z, y op z] - if z is a constant which (for op | its bitwise not) has n - consecutive least significant bits cleared followed by m 1 - consecutive bits set immediately above it and either - m + n == precision, or (x >> (m + n)) == (y >> (m + n)). - The least significant n bits of all the values in the range are - cleared or set, the m bits above it are preserved and any bits - above these are required to be the same for all values in the - range. */ - if (vr0p && range_int_cst_p (vr0p)) + [x, y] op z into [x op z, y op z]. */ + if (vr0p && range_int_cst_p (vr0p) + && range_easy_mask_min_max (code, wi::to_wide (vr0p->min), + wi::to_wide (vr0p->max), + wi::to_wide (vr1p->min))) { - wide_int w = wi::to_wide (vr1p->min); - int m = 0, n = 0; - if (code == BIT_IOR_EXPR) - w = ~w; - if (wi::eq_p (w, 0)) - n = TYPE_PRECISION (expr_type); - else - { - n = wi::ctz (w); - w = ~(w | wi::mask (n, false, w.get_precision ())); - if (wi::eq_p (w, 0)) - m = TYPE_PRECISION (expr_type) - n; - else - m = wi::ctz (w) - n; - } - wide_int mask = wi::mask (m + n, true, w.get_precision ()); - if ((mask & wi::to_wide (vr0p->min)) - == (mask & wi::to_wide (vr0p->max))) - { - min = int_const_binop (code, vr0p->min, vr1p->min); - max = int_const_binop (code, vr0p->max, vr1p->min); - } + min = int_const_binop (code, vr0p->min, vr1p->min); + max = int_const_binop (code, vr0p->max, vr1p->min); } } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 608ca5658b5..946e26e29b4 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -112,8 +112,14 @@ extern bool range_int_cst_p (value_range *); extern int operand_less_p (tree, tree); extern bool find_case_label_range (gswitch *, tree, tree, size_t *, size_t *); extern bool find_case_label_index (gswitch *, size_t, tree, size_t *); +extern void zero_nonzero_bits_from_bounds (signop, const wide_int&, + const wide_int&, wide_int *, + wide_int *); extern bool zero_nonzero_bits_from_vr (const tree, value_range *, wide_int *, wide_int *); +extern bool range_easy_mask_min_max (tree_code, + const wide_int &lb, const wide_int &ub, + const wide_int &mask); extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); extern bool range_int_cst_singleton_p (value_range *); extern int value_inside_range (tree, tree, tree);