diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 8ace3c2..5e48d6e 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1416,6 +1416,7 @@ OBJS = \ print-rtl-function.o \ print-tree.o \ profile.o \ + range.o \ read-md.o \ read-rtl.o \ read-rtl-function.o \ @@ -2484,6 +2485,7 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/gimple.h \ $(srcdir)/gimple-ssa.h \ $(srcdir)/tree-chkp.c \ + $(srcdir)/range.h $(srcdir)/range.c \ $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c \ $(srcdir)/tree-cfg.c $(srcdir)/tree-ssa-loop-ivopts.c \ $(srcdir)/tree-dfa.c \ diff --git a/gcc/builtins.c b/gcc/builtins.c index 4f6c9c4..b5c9eb0 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see #include "tm_p.h" #include "stringpool.h" #include "tree-vrp.h" +#include "range.h" #include "tree-ssanames.h" #include "expmed.h" #include "optabs.h" @@ -2894,6 +2895,52 @@ builtin_memcpy_read_str (void *data, HOST_WIDE_INT offset, return c_readstr (str + offset, mode); } +/* If a range IR may have wrapped in such a way that we can guess the + range is positive, return TRUE and set PROBABLE_MAX_SIZE. + Otherwise, return FALSE and leave PROBABLE_MAX_SIZE unchanged. */ + +static bool +range_may_have_wrapped (irange ir, + unsigned HOST_WIDE_INT *probable_max_size) +{ + /* Code like: + + signed int n; + if (n < 100) + { + # RANGE [0, 99][0xffff8000, 0xffffffff] + _1 = (unsigned) n; + memcpy (a, b, _1) + } + + Produce a range allowing negative values of N. We can still use + the information and make a guess that N is not negative. */ + if (ir.num_pairs () != 2 + || ir.lower_bound () != 0) + return false; + + const_tree type = ir.get_type (); + unsigned precision = TYPE_PRECISION (type); + gcc_assert (TYPE_UNSIGNED (type)); + + /* Build a range with all the negatives: [0xffff8000, 0xffffffff]. */ + wide_int minus_one = wi::bit_not (wide_int::from (0, precision, UNSIGNED)); + wide_int smallest_neg = wi::lshift (minus_one, precision / 2 - 1); + irange negatives (type, smallest_neg, minus_one); + + irange orig_range = ir; + ir.intersect (negatives); + if (ir == negatives) + { + wide_int max = orig_range.upper_bound (0); // Get the 99 in [0, 99]. + if (!wi::fits_uhwi_p (max)) + return false; + *probable_max_size = max.to_uhwi (); + return true; + } + return false; +} + /* LEN specify length of the block of memcpy/memset operation. Figure out its range and put it into MIN_SIZE/MAX_SIZE. In some cases we can make very likely guess on max size, then we @@ -2913,7 +2960,6 @@ determine_block_size (tree len, rtx len_rtx, else { wide_int min, max; - enum value_range_type range_type = VR_UNDEFINED; /* Determine bounds from the type. */ if (tree_fits_uhwi_p (TYPE_MIN_VALUE (TREE_TYPE (len)))) @@ -2926,34 +2972,18 @@ determine_block_size (tree len, rtx len_rtx, else *probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx)); - if (TREE_CODE (len) == SSA_NAME) - range_type = get_range_info (len, &min, &max); - if (range_type == VR_RANGE) + if (TREE_CODE (len) == SSA_NAME && get_range_info (len, &min, &max)) { - if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ()) - *min_size = min.to_uhwi (); - if (wi::fits_uhwi_p (max) && *max_size > max.to_uhwi ()) - *probable_max_size = *max_size = max.to_uhwi (); - } - else if (range_type == VR_ANTI_RANGE) - { - /* Anti range 0...N lets us to determine minimal size to N+1. */ - if (min == 0) + irange ir (len); + if (range_may_have_wrapped (ir, probable_max_size)) + ; + else { - if (wi::fits_uhwi_p (max) && max.to_uhwi () + 1 != 0) - *min_size = max.to_uhwi () + 1; + if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ()) + *min_size = min.to_uhwi (); + if (wi::fits_uhwi_p (max) && *max_size > max.to_uhwi ()) + *probable_max_size = *max_size = max.to_uhwi (); } - /* Code like - - int n; - if (n < 100) - memcpy (a, b, n) - - Produce anti range allowing negative values of N. We still - can use the information and make a guess that N is not negative. - */ - else if (!wi::leu_p (max, 1 << 30) && wi::fits_uhwi_p (min)) - *probable_max_size = min.to_uhwi () - 1; } } gcc_checking_assert (*max_size <= @@ -3136,7 +3166,7 @@ check_sizes (int opt, tree exp, tree size, tree maxlen, tree src, tree objsize) bool exactsize = size && tree_fits_uhwi_p (size); if (size) - get_size_range (size, range); + get_size_range (size, range, /*range_starts_at=*/0); /* First check the number of bytes to be written against the maximum object size. */ diff --git a/gcc/calls.c b/gcc/calls.c index 91a4466..160d9b4 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -49,6 +49,7 @@ along with GCC; see the file COPYING3. If not see #include "rtl-iter.h" #include "tree-chkp.h" #include "tree-vrp.h" +#include "range.h" #include "tree-ssanames.h" #include "rtl-chkp.h" #include "intl.h" @@ -1256,10 +1257,12 @@ alloc_max_size (void) after adjusting it if necessary to make EXP a valid size argument to an allocation function declared with attribute alloc_size (whose argument may be signed), or to a string manipulation function like - memset. */ + memset. + + RANGE_STARTS_AT is the number where the range will start from. */ bool -get_size_range (tree exp, tree range[2]) +get_size_range (tree exp, tree range[2], unsigned range_starts_at) { if (tree_fits_uhwi_p (exp)) { @@ -1269,74 +1272,41 @@ get_size_range (tree exp, tree range[2]) } wide_int min, max; - enum value_range_type range_type - = ((TREE_CODE (exp) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (exp))) - ? get_range_info (exp, &min, &max) : VR_VARYING); - - if (range_type == VR_VARYING) + if (TREE_CODE (exp) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (exp)) + || !get_range_info (exp, &min, &max)) { /* No range information available. */ range[0] = NULL_TREE; range[1] = NULL_TREE; return false; } + irange ir (exp); tree exptype = TREE_TYPE (exp); - unsigned expprec = TYPE_PRECISION (exptype); - wide_int wzero = wi::zero (expprec); - wide_int wmaxval = wide_int (TYPE_MAX_VALUE (exptype)); - - bool signed_p = !TYPE_UNSIGNED (exptype); - if (range_type == VR_ANTI_RANGE) + /* Remove negative numbers from the range. */ + irange positives; + range_positives (&positives, exptype, range_starts_at); + if (!positives.intersect (ir).empty_p ()) { - if (signed_p) - { - if (wi::les_p (max, wzero)) - { - /* EXP is not in a strictly negative range. That means - it must be in some (not necessarily strictly) positive - range which includes zero. Since in signed to unsigned - conversions negative values end up converted to large - positive values, and otherwise they are not valid sizes, - the resulting range is in both cases [0, TYPE_MAX]. */ - min = wzero; - max = wmaxval; - } - else if (wi::les_p (min - 1, wzero)) - { - /* EXP is not in a negative-positive range. That means EXP - is either negative, or greater than max. Since negative - sizes are invalid make the range [MAX + 1, TYPE_MAX]. */ - min = max + 1; - max = wmaxval; - } - else - { - max = min - 1; - min = wzero; - } - } - else if (wi::eq_p (wzero, min - 1)) - { - /* EXP is unsigned and not in the range [1, MAX]. That means - it's either zero or greater than MAX. Even though 0 would - normally be detected by -Walloc-zero set the range to - [MAX, TYPE_MAX] so that when MAX is greater than the limit - the whole range is diagnosed. */ - min = max + 1; - max = wmaxval; - } - else - { - max = min - 1; - min = wzero; - } + /* Remove the unknown parts of a multi-range. + This will transform [5,10][20,MAX] into [5,10]. */ + if (positives.num_pairs () > 1 + && positives.upper_bound () == wide_int (TYPE_MAX_VALUE (exptype))) + positives.remove_pair (positives.num_pairs () - 1); + + range[0] = wide_int_to_tree (exptype, positives.lower_bound ()); + range[1] = wide_int_to_tree (exptype, positives.upper_bound ()); + } + else + { + /* If removing the negative numbers didn't give us anything + back, the entire range was negative. Leave things as they + were, and let the caller sort it out. */ + range[0] = wide_int_to_tree (exptype, min); + range[1] = wide_int_to_tree (exptype, max); } - - range[0] = wide_int_to_tree (exptype, min); - range[1] = wide_int_to_tree (exptype, max); - return true; } diff --git a/gcc/calls.h b/gcc/calls.h index df5817f..2b204c7 100644 --- a/gcc/calls.h +++ b/gcc/calls.h @@ -38,6 +38,6 @@ extern bool pass_by_reference (CUMULATIVE_ARGS *, machine_mode, extern bool reference_callee_copied (CUMULATIVE_ARGS *, machine_mode, tree, bool); extern void maybe_warn_alloc_args_overflow (tree, tree, tree[2], int[2]); -extern bool get_size_range (tree, tree[2]); +extern bool get_size_range (tree, tree[2], unsigned range_starts_at = 1); #endif // GCC_CALLS_H diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 736552c..ec7b5ee 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -76,6 +76,7 @@ along with GCC; see the file COPYING3. If not see #include "md5.h" #include "case-cfn-macros.h" #include "stringpool.h" +#include "range.h" #include "tree-vrp.h" #include "tree-ssanames.h" #include "selftest.h" @@ -9063,7 +9064,6 @@ bool expr_not_equal_to (tree t, const wide_int &w) { wide_int min, max, nz; - value_range_type rtype; switch (TREE_CODE (t)) { case INTEGER_CST: @@ -9072,18 +9072,12 @@ expr_not_equal_to (tree t, const wide_int &w) case SSA_NAME: if (!INTEGRAL_TYPE_P (TREE_TYPE (t))) return false; - rtype = get_range_info (t, &min, &max); - if (rtype == VR_RANGE) + if (SSA_NAME_RANGE_INFO (t)) { - if (wi::lt_p (max, w, TYPE_SIGN (TREE_TYPE (t)))) - return true; - if (wi::lt_p (w, min, TYPE_SIGN (TREE_TYPE (t)))) + irange ri (t); + if (!ri.contains_p (w)) return true; } - else if (rtype == VR_ANTI_RANGE - && wi::le_p (min, w, TYPE_SIGN (TREE_TYPE (t))) - && wi::le_p (w, max, TYPE_SIGN (TREE_TYPE (t)))) - return true; /* If T has some known zero bits and W has any of those bits set, then T is known not to be equal to W. */ if (wi::ne_p (wi::zext (wi::bit_and_not (w, get_nonzero_bits (t)), diff --git a/gcc/function-tests.c b/gcc/function-tests.c index ca30028..f1f884d 100644 --- a/gcc/function-tests.c +++ b/gcc/function-tests.c @@ -574,6 +574,19 @@ test_conversion_to_ssa () ASSERT_EQ (SSA_NAME, TREE_CODE (gimple_return_retval (return_stmt))); } +/* Test the irange class. We must start this here because we need + cfun set. */ + +static void +test_iranges () +{ + tree fndecl = build_trivial_high_gimple_function (); + function *fun = DECL_STRUCT_FUNCTION (fndecl); + push_cfun (fun); + irange_tests (); + pop_cfun (); +} + /* Test of expansion from gimple-ssa to RTL. */ static void @@ -677,6 +690,7 @@ function_tests_c_tests () test_gimplification (); test_building_cfg (); test_conversion_to_ssa (); + test_iranges (); test_expansion_to_rtl (); } diff --git a/gcc/gengtype-parse.c b/gcc/gengtype-parse.c index f6ad398..37e678a 100644 --- a/gcc/gengtype-parse.c +++ b/gcc/gengtype-parse.c @@ -300,6 +300,13 @@ require_template_declaration (const char *tmpl_name) { if (T.code == '*') { + /* Handle simple multiplication by a constant. Do not + treat it like indirection. */ + if (token () == NUM) + { + str = concat (str, advance (), (char *) 0); + continue; + } id = "*"; if (num_indirections++) parse_error ("only one level of indirection is supported" diff --git a/gcc/gengtype.c b/gcc/gengtype.c index b02e9ff..1c281c3 100644 --- a/gcc/gengtype.c +++ b/gcc/gengtype.c @@ -1715,6 +1715,7 @@ open_base_files (void) "optabs.h", "libfuncs.h", "debug.h", "internal-fn.h", "gimple-fold.h", "tree-eh.h", "gimple-iterator.h", "gimple-ssa.h", "tree-cfg.h", "tree-vrp.h", "tree-phinodes.h", "ssa-iterators.h", "stringpool.h", + "range.h", "tree-ssanames.h", "tree-ssa-loop.h", "tree-ssa-loop-ivopts.h", "tree-ssa-loop-manip.h", "tree-ssa-loop-niter.h", "tree-into-ssa.h", "tree-dfa.h", "tree-ssa.h", "reload.h", "cpp-id-data.h", "tree-chrec.h", diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c index c99dfe1..658d7e6 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -2109,22 +2109,17 @@ dump_ssaname_info (pretty_printer *buffer, tree node, int spc) } } - if (!POINTER_TYPE_P (TREE_TYPE (node)) - && SSA_NAME_RANGE_INFO (node)) + if (!POINTER_TYPE_P (TREE_TYPE (node)) && SSA_NAME_RANGE_INFO (node)) { - wide_int min, max, nonzero_bits; - value_range_type range_type = get_range_info (node, &min, &max); + irange ri (node); + wide_int nonzero_bits; - if (range_type == VR_VARYING) + if (ri.empty_p ()) pp_printf (buffer, "# RANGE VR_VARYING"); - else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE) + else { pp_printf (buffer, "# RANGE "); - pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~"); - pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node))); - pp_printf (buffer, ", "); - pp_wide_int (buffer, max, TYPE_SIGN (TREE_TYPE (node))); - pp_printf (buffer, "]"); + ri.dump (buffer); } nonzero_bits = get_nonzero_bits (node); if (nonzero_bits != -1) diff --git a/gcc/gimple-ssa-sprintf.c b/gcc/gimple-ssa-sprintf.c index f43778b..0dd87a4 100644 --- a/gcc/gimple-ssa-sprintf.c +++ b/gcc/gimple-ssa-sprintf.c @@ -1132,8 +1132,7 @@ get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax, { /* Try to determine the range of values of the integer argument. */ wide_int min, max; - enum value_range_type range_type = get_range_info (arg, &min, &max); - if (range_type == VR_RANGE) + if (get_range_info (arg, &min, &max)) { HOST_WIDE_INT type_min = (TYPE_UNSIGNED (argtype) @@ -1432,8 +1431,7 @@ format_integer (const directive &dir, tree arg) /* Try to determine the range of values of the integer argument (range information is not available for pointers). */ wide_int min, max; - enum value_range_type range_type = get_range_info (arg, &min, &max); - if (range_type == VR_RANGE) + if (get_range_info (arg, &min, &max)) { argmin = wide_int_to_tree (argtype, min); argmax = wide_int_to_tree (argtype, max); @@ -1449,11 +1447,7 @@ format_integer (const directive &dir, tree arg) res.argmin = argmin; res.argmax = argmax; } - else if (range_type == VR_ANTI_RANGE) - { - /* Handle anti-ranges if/when bug 71690 is resolved. */ - } - else if (range_type == VR_VARYING) + else { /* The argument here may be the result of promoting the actual argument to int. Try to determine the type of the actual @@ -3877,9 +3871,7 @@ pass_sprintf_length::handle_gimple_call (gimple_stmt_iterator *gsi) and use the greater of the two at level 1 and the smaller of them at level 2. */ wide_int min, max; - enum value_range_type range_type - = get_range_info (size, &min, &max); - if (range_type == VR_RANGE) + if (get_range_info (size, &min, &max)) { dstsize = (warn_level < 2 diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c index ec95cc6..df506bb 100644 --- a/gcc/gimple-ssa-warn-alloca.c +++ b/gcc/gimple-ssa-warn-alloca.c @@ -216,13 +216,12 @@ alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, unsigned max_size) && TREE_CODE (limit) == SSA_NAME) { wide_int min, max; - value_range_type range_type = get_range_info (limit, &min, &max); - if (range_type == VR_UNDEFINED || range_type == VR_VARYING) + if (!get_range_info (limit, &min, &max)) return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN); // ?? It looks like the above `if' is unnecessary, as we never - // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range + // get any range information here. If we had a range // for LIMIT, I suppose we would have taken care of it in // alloca_call_type(), or handled above where we handle (ARG .COND. N). // @@ -252,13 +251,12 @@ cast_from_signed_p (tree ssa, tree *invalid_casted_type) return false; } -// Return TRUE if X has a maximum range of MAX, basically covering the -// entire domain, in which case it's no range at all. +// Return TRUE if TYPE has a maximum range of MAX. static bool -is_max (tree x, wide_int max) +is_max (tree type, wide_int max) { - return wi::max_value (TREE_TYPE (x)) == max; + return wi::max_value (type) == max; } // Analyze the alloca call in STMT and return the alloca type with its @@ -284,104 +282,103 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) // Adjust warn_alloca_max_size for VLAs, by taking the underlying // type into account. - unsigned HOST_WIDE_INT max_size; + unsigned HOST_WIDE_INT max_user_size; if (is_vla) - max_size = (unsigned HOST_WIDE_INT) warn_vla_limit; + max_user_size = (unsigned HOST_WIDE_INT) warn_vla_limit; else - max_size = (unsigned HOST_WIDE_INT) warn_alloca_limit; + max_user_size = (unsigned HOST_WIDE_INT) warn_alloca_limit; // Check for the obviously bounded case. if (TREE_CODE (len) == INTEGER_CST) { - if (tree_to_uhwi (len) > max_size) + if (tree_to_uhwi (len) > max_user_size) return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE, len); if (integer_zerop (len)) return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO); ret = alloca_type_and_limit (ALLOCA_OK); } // Check the range info if available. - else if (TREE_CODE (len) == SSA_NAME) + else if (TREE_CODE (len) == SSA_NAME && get_range_info (len, &min, &max)) { - value_range_type range_type = get_range_info (len, &min, &max); - if (range_type == VR_RANGE) + irange r (len); + if (wi::leu_p (max, max_user_size)) + ret = alloca_type_and_limit (ALLOCA_OK); + else if (is_max (TREE_TYPE (len), max) + && !r.range_for_type_p () + && cast_from_signed_p (len, invalid_casted_type)) { - if (wi::leu_p (max, max_size)) - ret = alloca_type_and_limit (ALLOCA_OK); - else - { - // A cast may have created a range we don't care - // about. For instance, a cast from 16-bit to - // 32-bit creates a range of 0..65535, even if there - // is not really a determinable range in the - // underlying code. In this case, look through the - // cast at the original argument, and fall through - // to look at other alternatives. - // - // We only look at through the cast when its from - // unsigned to unsigned, otherwise we may risk - // looking at SIGNED_INT < N, which is clearly not - // what we want. In this case, we'd be interested - // in a VR_RANGE of [0..N]. - // - // Note: None of this is perfect, and should all go - // away with better range information. But it gets - // most of the cases. - gimple *def = SSA_NAME_DEF_STMT (len); - if (gimple_assign_cast_p (def)) - { - tree rhs1 = gimple_assign_rhs1 (def); - tree rhs1type = TREE_TYPE (rhs1); - - // Bail if the argument type is not valid. - if (!INTEGRAL_TYPE_P (rhs1type)) - return alloca_type_and_limit (ALLOCA_OK); - - if (TYPE_UNSIGNED (rhs1type)) - { - len_casted = rhs1; - range_type = get_range_info (len_casted, &min, &max); - } - } - // An unknown range or a range of the entire domain is - // really no range at all. - if (range_type == VR_VARYING - || (!len_casted && is_max (len, max)) - || (len_casted && is_max (len_casted, max))) - { - // Fall through. - } - else if (range_type == VR_ANTI_RANGE) - return alloca_type_and_limit (ALLOCA_UNBOUNDED); - else if (range_type != VR_VARYING) - return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max); - } - } - else if (range_type == VR_ANTI_RANGE) - { - // There may be some wrapping around going on. Catch it - // with this heuristic. Hopefully, this VR_ANTI_RANGE - // nonsense will go away, and we won't have to catch the - // sign conversion problems with this crap. + // A cast from signed to unsigned may cause us to have very + // large numbers that can be caught with the above + // heuristic. // // This is here to catch things like: // void foo(signed int n) { // if (n < 100) - // alloca(n); + // { + // # RANGE [0,99][0xff80, 0xffff] + // unsigned int _1 = (unsigned int) n; + // alloca (_1); + // } // ... // } - if (cast_from_signed_p (len, invalid_casted_type)) + // + // Unfortunately it also triggers: + // + // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah; + // if (n < 100) + // alloca(n); + // + // ...which is clearly bounded. So, double check that + // the paths leading up to the size definitely don't + // have a bound. + tentative_cast_from_signed = true; + } + else + { + // A cast may have created a range we don't care + // about. For instance, a cast from 16-bit to + // 32-bit creates a range of 0..65535, even if there + // is not really a determinable range in the + // underlying code. In this case, look through the + // cast at the original argument, and fall through + // to look at other alternatives. + // + // We only look through the cast when it's from unsigned to + // unsigned, otherwise we risk looking at SIGNED_INT < N, + // which is clearly not what we want. In this case, we'd be + // interested in a VR_RANGE of [0..N]. + // + // Note: None of this is perfect, and should all go + // away with better range information. But it gets + // most of the cases. + gimple *def = SSA_NAME_DEF_STMT (len); + bool have_range = true; + if (gimple_assign_cast_p (def)) + + { + tree rhs1 = gimple_assign_rhs1 (def); + tree rhs1type = TREE_TYPE (rhs1); + + // Bail if the argument type is not valid. + if (!INTEGRAL_TYPE_P (rhs1type)) + return alloca_type_and_limit (ALLOCA_OK); + + if (TYPE_UNSIGNED (rhs1type)) + { + len_casted = rhs1; + have_range = get_range_info (len_casted, &min, &max); + } + } + // An unknown range or a range of the entire domain is + // really no range at all. + if (!have_range + || (!len_casted && is_max (TREE_TYPE (len), max)) + || (len_casted && is_max (TREE_TYPE (len_casted), max))) { - // Unfortunately this also triggers: - // - // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah; - // if (n < 100) - // alloca(n); - // - // ...which is clearly bounded. So, double check that - // the paths leading up to the size definitely don't - // have a bound. - tentative_cast_from_signed = true; + // Fall through. } + else + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max); } // No easily determined range and try other things. } @@ -397,7 +394,7 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) { gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted))); ret = alloca_call_type_by_arg (len, len_casted, - EDGE_PRED (bb, ix), max_size); + EDGE_PRED (bb, ix), max_user_size); if (ret.type != ALLOCA_OK) break; } diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c index 75fe027..df6aa0a 100644 --- a/gcc/internal-fn.c +++ b/gcc/internal-fn.c @@ -496,7 +496,7 @@ get_min_precision (tree arg, signop sign) if (TREE_CODE (arg) != SSA_NAME) return prec + (orig_sign != sign); wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (!get_range_info (arg, &arg_min, &arg_max)) { gimple *g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index b97d7af..94f50c1 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -981,8 +981,6 @@ ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask) void ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp) { - wide_int get_nonzero_bits (const_tree); - if (TREE_CODE (operand) == INTEGER_CST) { *valuep = wi::to_widest (operand); diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 10741a2..c1e034f 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -1896,7 +1896,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi, value_range_type type; if (TREE_CODE (arg) == SSA_NAME && param_type - && (type = get_range_info (arg, &min, &max)) + && (type = get_range_info_as_value_range (arg, &min, &max)) && (type == VR_RANGE || type == VR_ANTI_RANGE)) { value_range tmpvr,resvr; @@ -1906,6 +1906,18 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi, tmpvr.max = wide_int_to_tree (TREE_TYPE (arg), max); tmpvr.equiv = NULL; memset (&resvr, 0, sizeof (resvr)); + /* FIXME: Can we rewrite this to avoid calling the + internals of VRP here? We should really get rid of + the call to get_range_info_as_value_range() above, + and this value_range business throughout this file. + + At this point, we should only be looking at + SSA_NAME_RANGE_INFO (through get_range_info()). + + Perhaps we could look at all the uses of value_range + in this file, and if they are only used on + INTEGRAL_TYPE_P's, rewrite this to use the irage + class. */ extract_range_from_unary_expr (&resvr, NOP_EXPR, param_type, &tmpvr, TREE_TYPE (arg)); if (resvr.type == VR_RANGE || resvr.type == VR_ANTI_RANGE) diff --git a/gcc/range.c b/gcc/range.c new file mode 100644 index 0000000..e2ca95c --- /dev/null +++ b/gcc/range.c @@ -0,0 +1,1361 @@ +/* SSA range analysis implementation. -*- C++ -*- + Copyright (C) 2017 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "gimple-pretty-print.h" +#include "fold-const.h" +#include "ssa.h" +#include "range.h" +#include "selftest.h" + +/* Set range from a TYPE and some bounds (LBOUND and UBOUND). + + RT is PLAIN if it is a normal range, or INVERSE if it is an inverse + range. */ + +void +irange::set_range (const_tree typ, const wide_int &lbound, + const wide_int &ubound, kind rt) +{ + gcc_assert (INTEGRAL_TYPE_P (typ) || POINTER_TYPE_P (typ)); + gcc_assert (TYPE_PRECISION (typ) == lbound.get_precision ()); + gcc_assert (lbound.get_precision () == ubound.get_precision ()); + overflow = false; + type = typ; + gcc_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type))); + if (rt == INVERSE) + { + /* We calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. */ + bool ovf; + nitems = 0; + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + + /* If we will overflow, don't bother. This will handle unsigned + underflow which doesn't set the overflow bit. + + Note: Perhaps all these &ovf checks are unecessary since we + are manually checking for overflow with the if() below. */ + if (lbound != min) + { + bounds[nitems++] = min; + bounds[nitems++] = wi::sub (lbound, 1, TYPE_SIGN (type), &ovf); + if (ovf) + nitems = 0; + } + /* If we will overflow, don't bother. This will handle unsigned + overflow which doesn't set the overflow bit. */ + if (ubound != max) + { + bounds[nitems++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf); + if (ovf) + nitems--; + else + bounds[nitems++] = max; + } + + /* If we get here with N==0, it means we tried to calculate the + inverse of [-MIN, +MAX] which is actually the empty set, and + N==0 maps nicely to the empty set :). */ + } + else + { + nitems = 2; + bounds[0] = lbound; + bounds[1] = ubound; + } +} + +// Set range from an IRANGE_STORAGE and TYPE. + +void +irange::set_range (const irange_storage *storage, const_tree typ) +{ + overflow = false; + type = typ; + nitems = 0; + unsigned i = 0; + unsigned precision = wi::get_precision (storage->trailing_bounds[0]); + gcc_assert (precision == TYPE_PRECISION (typ)); + while (i < max_pairs * 2) + { + wide_int lo = storage->trailing_bounds[i]; + wide_int hi = storage->trailing_bounds[i + 1]; + // A nonsensical sub-range of [1,0] marks the end of valid ranges. + if (lo == wi::one (precision) && hi == wi::zero (precision)) + break; + bounds[i] = lo; + bounds[i + 1] = hi; + i += 2; + } + nitems = i; + gcc_assert (nitems <= max_pairs * 2); +} + +/* Set range from an SSA_NAME's available range. If there is no + available range, build a range for its entire domain. */ + +void +irange::set_range (const_tree ssa) +{ + tree t = TREE_TYPE (ssa); + gcc_assert (TREE_CODE (ssa) == SSA_NAME && INTEGRAL_TYPE_P (t)); + if (!SSA_NAME_RANGE_INFO (ssa)) + { + set_range_for_type (t); + return; + } + irange_storage *storage = SSA_NAME_RANGE_INFO (ssa); + set_range (storage, t); +} + +/* Set range from the full domain of type T. */ + +void +irange::set_range_for_type (const_tree t) +{ + gcc_assert (TYPE_P (t)); + gcc_assert (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t)); + wide_int min = wi::min_value (TYPE_PRECISION (t), TYPE_SIGN (t)); + wide_int max = wi::max_value (TYPE_PRECISION (t), TYPE_SIGN (t)); + set_range (t, min, max); +} + +irange::irange (const irange &r) +{ + type = r.type; + overflow = false; + nitems = r.nitems; + for (unsigned i = 0; i < nitems; ++i) + bounds[i] = r.bounds[i]; +} + +bool +irange::operator== (const irange &r) const +{ + if (type != r.type || nitems != r.nitems || overflow != r.overflow) + return false; + for (unsigned i = 0; i < nitems; ++i) + if (bounds[i] != r.bounds[i]) + return false; + return true; +} + +irange& +irange::operator= (const irange &r) +{ + type = r.type; + nitems = r.nitems; + overflow = r.overflow; + for (unsigned i = 0; i < nitems; ++i) + bounds[i] = r.bounds[i]; + return *this; +} + + +irange& +irange::operator= (const_tree t) +{ + set_range (t); + return *this; +} + +// Return true if this range is the full range for it's type + +bool +irange::range_for_type_p () const +{ + irange tmp; + tmp.set_range_for_type (type); + return (*this == tmp); +} + + +bool +irange::valid_p () const +{ + if (!nitems + || nitems % 2 + || nitems > max_pairs * 2) + return false; + + /* Check that the bounds are in the right order. + + So for [a,b][c,d][e,f] we must have: + a <= b < c <= d < e <= f. */ + if (wi::gt_p (bounds[0], bounds[1], TYPE_SIGN (type))) + return false; + for (unsigned i = 2; i < nitems; i += 2) + { + if (wi::le_p (bounds[i], bounds[i-1], TYPE_SIGN (type))) + return false; + if (wi::gt_p (bounds[i], bounds[i+1], TYPE_SIGN (type))) + return false; + } + return true; +} + +/* Convert the current range in place into a range of type NEW_TYPE. + The type of the original range is changed to the new type. */ + +void +irange::cast (const_tree new_type) +{ + if (!nitems) + { + type = new_type; + return; + } + bool sign_change = TYPE_SIGN (new_type) != TYPE_SIGN (type); + unsigned new_precision = TYPE_PRECISION (new_type); + + /* If nothing changed, this may be a useless type conversion between + two variants of the same type. */ + if (!sign_change && TYPE_PRECISION (type) == new_precision) + { + type = new_type; + return; + } + + /* If any of the old bounds are outside of the representable range + for the new type, conservatively default to the entire range of + the new type. */ + if (new_precision < TYPE_PRECISION (type)) + { + /* NOTE: There are some const_cast<> sprinkled throughout + because the fold_convert machinery is not properly + constified. */ + /* Get the extreme bounds for the new type, but within the old type, + so we can properly compare them. */ + wide_int lbound = fold_convert (const_cast (type), + TYPE_MIN_VALUE (new_type)); + wide_int ubound + = fold_convert (const_cast (type), + TYPE_MAX_VALUE (new_type)); + + if (wi::lt_p (bounds[0], lbound, TYPE_SIGN (type)) + || wi::gt_p (bounds[nitems - 1], ubound, TYPE_SIGN (type))) + { + bounds[0] = wide_int::from (lbound, new_precision, + TYPE_SIGN (new_type)); + bounds[1] = wide_int::from (ubound, new_precision, + TYPE_SIGN (new_type)); + type = new_type; + nitems = 2; + return; + } + } + + wide_int orig_low = lower_bound (); + wide_int orig_high = upper_bound (); + wide_int min = wi::min_value (new_precision, TYPE_SIGN (new_type)); + wide_int max = wi::max_value (new_precision, TYPE_SIGN (new_type)); + for (unsigned i = 0; i < nitems; i += 2) + { + tree b0 + = fold_convert (const_cast (new_type), + wide_int_to_tree (const_cast (type), + bounds[i])); + tree b1 + = fold_convert (const_cast (new_type), + wide_int_to_tree (const_cast (type), + bounds[i+1])); + bool sbit0 = bounds[i].sign_mask () < 0; + bool sbit1 = bounds[i + 1].sign_mask () < 0; + + /* If we're not doing a sign change, or we are moving to a + higher precision, we can just blindly chop off bits. */ + if (!sign_change + || (TYPE_UNSIGNED (type) + && !TYPE_UNSIGNED (new_type) + && new_precision > TYPE_PRECISION (type)) + || sbit0 == sbit1) + { + bounds[i] = b0; + bounds[i + 1] = b1; + } + else + { + /* If we're about to go over the maximum number of ranges + allowed, convert to something conservative and cast + again. */ + if (nitems >= max_pairs * 2) + { + bounds[0] = orig_low; + bounds[1] = orig_high; + nitems = 2; + cast (new_type); + return; + } + /* If we're about to construct [MIN, b1==MAX]. That's just + the entire range. */ + if ((wide_int) b1 == max) + { + bounds[0] = min; + bounds[1] = max; + nitems = 2; + type = new_type; + return; + } + /* From no sign bit to sign bit: [15, 150] + => [15,127][-128,-106]. */ + if (!sbit0 && sbit1) + { + bounds[i] = min; + bounds[i + 1] = b1; + bounds[nitems++] = b0; + bounds[nitems++] = max; + } + /* From sign bit to no sign bit: [-5, 5] + => [251,255][0,5]. */ + else + { + bounds[i] = min; + bounds[i + 1] = b1; + bounds[nitems++] = b0; + bounds[nitems++] = max; + } + } + } + type = new_type; + if (sign_change) + canonicalize (); + gcc_assert (valid_p ()); +} + +// Return TRUE if the current range contains ELEMENT. + +bool +irange::contains_p (const wide_int &element) const +{ + for (unsigned i = 0; i < nitems; i += 2) + if (wi::ge_p (element, bounds[i], TYPE_SIGN (type)) + && wi::le_p (element, bounds[i + 1], TYPE_SIGN (type))) + return true; + return false; +} + +// Like above, but ELEMENT can be an INTEGER_CST of any type. + +bool +irange::contains_p (const_tree element) const +{ + gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (element))); + tree t = fold_convert (const_cast (type), + const_cast (element)); + if (TREE_OVERFLOW (t)) + return false; + wide_int wi = t; + return contains_p (wi); +} + +// Canonicalize the current range. + +void +irange::canonicalize () +{ + if (nitems < 2) + return; + + /* Fix any out of order ranges: [10,20][-5,5] into [-5,5][10,20]. + + This is not a true sort by design because I *think* we won't + create any truly wacky ranges during casting. As a temporary + measure, check assert(valid_p()) afterwards and if we catch + anything, rewrite this into a bubble sort. */ + for (unsigned i = 0; i < (unsigned) (nitems - 2); i += 2) + if (wi::gt_p (bounds[i], bounds[i + 2], TYPE_SIGN (type))) + { + wide_int x = bounds[i], y = bounds[i + 1]; + bounds[i] = bounds[i + 2]; + bounds[i + 1] = bounds[i + 3]; + bounds[i + 2] = x; + bounds[i + 3] = y; + } + gcc_assert (valid_p ()); // See note before for(;;). + + /* Merge any edges that touch. + [9,10][11,20] => [9,20]. */ + for (unsigned i = 1; i < (unsigned) (nitems - 2); i += 2) + { + bool ovf; + wide_int x = wi::add (bounds[i], 1, TYPE_SIGN (type), &ovf); + /* No need to check for overflow here for the +1, since the + middle ranges cannot have MAXINT. */ + if (x == bounds[i + 1]) + { + bounds[i] = bounds[i + 2]; + remove (i + 1, i + 2); + } + } +} + +// Prepend [X,Y] into THIS. + +void +irange::prepend (const wide_int &x, const wide_int &y) +{ + /* If we have enough space, shift everything to the right and + prepend. */ + if (nitems < max_pairs * 2) + { + for (unsigned i = nitems; i; i -= 2) + { + bounds[i] = bounds[i - 2]; + bounds[i + 1] = bounds[i - 1]; + } + bounds[0] = x; + bounds[1] = y; + nitems += 2; + } + /* Otherwise, merge it with the first entry. */ + else + bounds[0] = x; + canonicalize (); +} + +// Place [X,Y] at the end of THIS. + +void +irange::append (const wide_int &x, const wide_int &y) +{ + /* If we have enough space, make space at the end and append. */ + if (nitems < max_pairs * 2) + { + bounds[nitems++] = x; + bounds[nitems++] = y; + } + /* Otherwise, merge it with the last entry. */ + else + bounds[nitems - 1] = y; + canonicalize (); +} + +// Remove the bound entries from [i..j]. + +void +irange::remove (unsigned i, unsigned j) +{ + gcc_assert (i < nitems && i < j); + unsigned dst = i; + unsigned ndeleted = j - i + 1; + for (++j; j < nitems; ++j) + bounds[dst++] = bounds[j]; + nitems -= ndeleted; +} + +// THIS = THIS U [X,Y] + +irange & +irange::union_ (const wide_int &x, const wide_int &y) +{ + if (empty_p ()) + { + bounds[0] = x; + bounds[1] = y; + nitems = 2; + return *this; + } + + /* If [X,Y] comes before, put it at the front. */ + if (wi::lt_p (y, bounds[0], TYPE_SIGN (type))) + { + prepend (x, y); + return *this; + } + /* If [X,Y] comes after, put it at the end. */ + if (wi::gt_p (x, bounds[nitems - 1], TYPE_SIGN (type))) + { + append (x, y); + return *this; + } + /* Handle [X,Y] swalling up all of THIS. */ + if (wi::le_p (x, bounds[0], TYPE_SIGN (type)) + && wi::ge_p (y, bounds[nitems - 1], TYPE_SIGN (type))) + { + bounds[0] = x; + bounds[1] = y; + nitems = 2; + return *this; + } + /* Handle X starting before, while Y is within. + Y + X[a,b][c,d][e,f][g,h][i,j] + ==> [X,Y][g,h][i,j]. */ + if (wi::lt_p (x, bounds[0], TYPE_SIGN (type))) + { + bounds[0] = x; + + /* Y + X[a,b] => [X,b]. */ + if (nitems == 2) + return *this; + + for (unsigned i = 1; i < nitems; i += 2) + if (wi::le_p (y, bounds[i], TYPE_SIGN (type))) + { + if (y == bounds[i]) + bounds[1] = y; + else + bounds[1] = bounds[i]; + remove (2, i); + return *this; + } + gcc_unreachable (); + } + /* Handle Y being outside, while X is within. + X Y + [a,b][c,d][e,f][g,h][i,j] + ==> [a,b][c,d][e,Y]. */ + if (wi::gt_p (y, bounds[nitems - 1], TYPE_SIGN (type))) + { + for (unsigned i = 0; i < nitems; i += 2) + if (wi::ge_p (bounds[i + 1], x, TYPE_SIGN (type))) + { + bounds[i + 1] = y; + nitems = i + 2; + return *this; + } + gcc_unreachable (); + } + + /* At this point, [X,Y] must be completely inside. + X Y + [a,b][c,d][e,f][g,h]. */ + gcc_assert (wi::ge_p (x, bounds[0], TYPE_SIGN (type)) + && wi::le_p (y, bounds[nitems - 1], TYPE_SIGN (type))); + + /* Find X. */ + gcc_assert (nitems >= 2); + unsigned xpos = ~0U; + unsigned i = nitems; + do + { + i -= 2; + if (wi::ge_p (x, bounds[i], TYPE_SIGN (type))) + { + xpos = i; + break; + } + } + while (i); + gcc_assert (xpos != ~0U); + + /* Find Y. */ + unsigned ypos = ~0U; + for (i = 1; i < nitems; i += 2) + if (wi::le_p (y, bounds[i], TYPE_SIGN (type))) + { + ypos = i; + break; + } + gcc_assert (ypos != ~0U); + + /* If [x,y] is inside of subrange [xpos,ypos], there's nothing to do. */ + if (xpos + 1 == ypos) + return *this; + + /* Merge the sub-ranges in between xpos and ypos. */ + wide_int tmp = bounds[ypos]; + remove (xpos + 2, ypos); + bounds[xpos + 1] = tmp; + + return *this; +} + +// THIS = THIS U R + +irange & +irange::union_ (const irange &r) +{ + gcc_assert (type == r.type); + + if (empty_p ()) + { + *this = r; + return *this; + } + else if (r.empty_p ()) + return *this; + + for (unsigned i = 0; i < r.nitems; i += 2) + union_ (r.bounds[i], r.bounds[i + 1]); + + overflow |= r.overflow; + return *this; +} + +// THIS = THIS ^ [X,Y]. + +irange & +irange::intersect (const wide_int &x, const wide_int &y) +{ + unsigned pos = 0; + + for (unsigned i = 0; i < nitems; i += 2) + { + wide_int newlo = wi::max (bounds[i], x, TYPE_SIGN (type)); + wide_int newhi = wi::min (bounds[i + 1], y, TYPE_SIGN (type)); + if (wi::gt_p (newlo, newhi, TYPE_SIGN (type))) + { + /* If the new sub-range doesn't make sense, it's an + impossible range and must be kept out of the result. */ + } + else + { + bounds[pos++] = newlo; + bounds[pos++] = newhi; + } + } + nitems = pos; + return *this; +} + +// THIS = THIS ^ R. + +irange & +irange::intersect (const irange &r) +{ + gcc_assert (type == r.type); + irange orig_range (*this); + + /* Intersection with an empty range is an empty range. */ + clear (); + if (orig_range.empty_p () || r.empty_p ()) + return *this; + + /* The general algorithm is as follows. + + Intersect each sub-range of R with all of ORIG_RANGE one at a time, and + join/union the results of these intersections together. I.e: + + [10,20][30,40][50,60] ^ [15,25][38,51][55,70] + + Step 1: [10,20][30,40][50,60] ^ [15,25] => [15,20] + Step 2: [10,20][30,40][50,60] ^ [38,51] => [38,40] + Step 3: [10,20][30,40][50,60] ^ [55,70] => [55,60] + Final: [15,20] U [38,40] U [55,60] => [15,20][38,40][55,60] + + ?? We should probably stop making a copy of ORIG_RANGE at every step. */ + for (unsigned i = 0; i < r.nitems; i += 2) + union_ (irange (orig_range).intersect (r.bounds[i], r.bounds[i + 1])); + + /* Overflow is sticky only if both ranges overflowed. */ + overflow = (orig_range.overflow && r.overflow); + return *this; +} + +// Set THIS to the inverse of its range. + +irange & +irange::invert () +{ + /* We always need one more set of bounds to represent an inverse, so + if we're at the limit, we can't properly represent things. + + For instance, to represent the inverse of a 2 sub-range set + [5, 10][20, 30], we would need a 3 sub-range set + [-MIN, 4][11, 19][31, MAX]. + + In this case convert the current range to something more + conservative, and return the inverse of that. + + However, if any of the extremes of the range are -MIN/+MAX, we + know we will not need an extra bound. For example: + + INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] + INVERT([-MIN,20][30,MAX]) => [21,29] + */ + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + if (nitems == max_pairs * 2 + && bounds[0] != min + && bounds[nitems] != max) + { + bounds[0] = bounds[0]; + bounds[1] = bounds[nitems - 1]; + nitems = 2; + return invert (); + } + + /* The inverse of the empty set is the entire domain. */ + if (empty_p ()) + { + set_range_for_type (type); + return *this; + } + + /* The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we + generate [-MIN, a-1][b+1, c-1][d+1, MAX]. + + If there is an over/underflow in the calculation for any + sub-range, we eliminate that subrange. This allows us to easily + calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since + we eliminate the underflow, only [6, MAX] remains. */ + + unsigned i = 0; + bool ovf; + + /* Construct leftmost range. */ + irange orig_range (*this); + nitems = 0; + /* If this is going to underflow on the MINUS 1, don't even bother + checking. This also handles subtracting one from an unsigned 0, + which doesn't set the underflow bit. */ + if (min != orig_range.bounds[i]) + { + bounds[nitems++] = min; + bounds[nitems++] + = wi::sub (orig_range.bounds[i], 1, TYPE_SIGN (type), &ovf); + if (ovf) + nitems = 0; + } + i++; + /* Construct middle ranges if applicable. */ + if (orig_range.nitems > 2) + { + unsigned j = i; + for (; j < (unsigned) (orig_range.nitems - 2); j += 2) + { + /* The middle ranges cannot have MAX/MIN, so there's no need + to check for unsigned overflow on the +1 and -1 here. */ + bounds[nitems++] + = wi::add (orig_range.bounds[j], 1, TYPE_SIGN (type), &ovf); + bounds[nitems++] + = wi::sub (orig_range.bounds[j + 1], 1, TYPE_SIGN (type), &ovf); + if (ovf) + nitems -= 2; + } + i = j; + } + /* Construct rightmost range. + + However, if this will overflow on the PLUS 1, don't even bother. + This also handles adding one to an unsigned MAX, which doesn't + set the overflow bit. */ + if (max != orig_range.bounds[i]) + { + bounds[nitems++] + = wi::add (orig_range.bounds[i], 1, TYPE_SIGN (type), &ovf); + bounds[nitems++] = max; + if (ovf) + nitems -= 2; + } + + return *this; +} + +/* Returns the upper bound of PAIR. */ + +wide_int +irange::upper_bound (unsigned pair) const +{ + gcc_assert (nitems != 0 && pair <= num_pairs ()); + return bounds[pair * 2 + 1]; +} + +/* Dump the current range onto BUFFER. */ + +void +irange::dump (pretty_printer *buffer) +{ + if (!nitems) + { + pp_string (buffer, "[]"); + return; + } + for (unsigned i = 0; i < nitems; ++i) + { + if (i % 2 == 0) + pp_character (buffer, '['); + wide_int val = bounds[i]; + print_hex (val, pp_buffer (buffer)->digit_buffer); + pp_string (buffer, pp_buffer (buffer)->digit_buffer); + if (i % 2 == 0) + pp_string (buffer, ", "); + else + pp_character (buffer, ']'); + } + if (overflow) + pp_string (buffer, "(overflow)"); + + pp_string (buffer, " precision = "); + pp_decimal_int (buffer, TYPE_PRECISION (type)); +} + +/* Dump the current range onto FILE F. */ + +void +irange::dump (FILE *f) +{ + pretty_printer buffer; + buffer.buffer->stream = f; + dump (&buffer); + pp_newline_and_flush (&buffer); +} + +/* Like above but dump to STDERR. + + ?? You'd think we could have a default parameter for dump(FILE), + but gdb currently doesn't do default parameters gracefully-- or at + all, and since this is a function we need to be callable from the + debugger... */ + +void +irange::dump () +{ + dump (stderr); +} + +/* Initialize the current irange_storage to the irange in IR. */ + +void +irange_storage::set_irange (const irange &ir) +{ + unsigned precision = TYPE_PRECISION (ir.get_type ()); + trailing_bounds.set_precision (precision); + unsigned i; + for (i = 0; i < ir.num_pairs () * 2; ++i) + trailing_bounds[i] = ir.bounds[i]; + + /* Build nonsensical [1,0] pairs for the remaining empty ranges. + These will be recognized as empty when we read the structure + back. */ + for (; i < irange::max_pairs * 2; i += 2) + { + trailing_bounds[i] = wi::one (precision); + trailing_bounds[i + 1] = wi::zero (precision); + } +} + +bool +make_irange (irange *result, const_tree lb, const_tree ub, const_tree type) +{ + irange r (TREE_TYPE (lb), lb, ub); + *result = r; + if (result->valid_p ()) + { + if (type) + result->cast (type); + return true; + } + return false; +} + +bool +make_irange_not (irange *result, const_tree not_exp, const_tree type) +{ + irange r (TREE_TYPE (not_exp), not_exp, not_exp, irange::INVERSE); + *result = r; + if (result->valid_p ()) + { + if (type) + result->cast (type); + return true; + } + return false; +} + +void +range_one (irange *r, tree type) +{ + tree one = build_int_cst (type, 1); + r->set_range (type, one, one); +} + +void +range_zero (irange *r, tree type) +{ + tree zero = build_int_cst (type, 0); + r->set_range (type, zero, zero); +} + +bool +range_non_zero (irange *r, tree type) +{ + tree zero = build_int_cst (type, 0); + return make_irange_not (r, zero, type); +} + +/* Set the range of R to the set of positive numbers starting at START. */ + +void +range_positives (irange *r, tree type, unsigned int start) +{ + r->set_range (type, build_int_cst (type, start), TYPE_MAX_VALUE (type)); +} + +#ifdef CHECKING_P +namespace selftest { + + +#define INT(N) build_int_cst (integer_type_node, (N)) +#define UINT(N) build_int_cstu (unsigned_type_node, (N)) +#define INT16(N) build_int_cst (short_integer_type_node, (N)) +#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N)) +#define INT64(N) build_int_cstu (long_long_integer_type_node, (N)) +#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N)) +#define UINT128(N) build_int_cstu (u128_type, (N)) +#define UCHAR(N) build_int_cst (unsigned_char_type_node, (N)) +#define SCHAR(N) build_int_cst (signed_char_type_node, (N)) + +#define RANGE1(A,B) irange (integer_type_node, INT(A), INT(B)) + +#define RANGE2(A,B,C,D) \ +( i1 = irange (integer_type_node, INT (A), INT (B)), \ + i2 = irange (integer_type_node, INT (C), INT (D)), \ + i1.union_ (i2), \ + i1 ) + +#define RANGE3(A,B,C,D,E,F) \ +( i1 = irange (integer_type_node, INT (A), INT (B)), \ + i2 = irange (integer_type_node, INT (C), INT (D)), \ + i3 = irange (integer_type_node, INT (E), INT (F)), \ + i1.union_ (i2), \ + i1.union_ (i3), \ + i1 ) + +// Run all of the selftests within this file. + +void +irange_tests () +{ + tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); + irange i1, i2, i3; + irange r0, r1, rold; + ASSERT_FALSE (r0.valid_p ()); + + /* Test that NOT(255) is [0..254] in 8-bit land. */ + irange not_255; + make_irange_not (¬_255, UCHAR(255), unsigned_char_type_node); + ASSERT_TRUE (not_255 == irange (unsigned_char_type_node, + UCHAR(0), UCHAR(254))); + + /* Test that NOT(0) is [1..255] in 8-bit land. */ + irange not_zero; + range_non_zero (¬_zero, unsigned_char_type_node); + ASSERT_TRUE (not_zero == irange (unsigned_char_type_node, + UCHAR(1), UCHAR(255))); + + /* Check that [0,127][0x..ffffff80,0x..ffffff] + => ~[128, 0x..ffffff7f]. */ + r0 = irange (u128_type, UINT128(0), UINT128(127), irange::PLAIN); + tree high = build_minus_one_cst (u128_type); + /* low = -1 - 127 => 0x..ffffff80. */ + tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); + r1 = irange (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff] + /* r0 = [0,127][0x..ffffff80,0x..fffffff]. */ + r0.union_ (r1); + /* r1 = [128, 0x..ffffff7f]. */ + r1 = irange (u128_type, + UINT128(128), + fold_build2 (MINUS_EXPR, u128_type, + build_minus_one_cst (u128_type), + UINT128(128))); + r0.invert (); + ASSERT_TRUE (r0 == r1); + + r0.set_range_for_type (integer_type_node); + tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ()); + tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); + + r0.set_range_for_type (short_integer_type_node); + tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ()); + tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ()); + + r0.set_range_for_type (unsigned_type_node); + tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); + + /* Check that ~[0,5] => [6,MAX] for unsigned int. */ + r0 = irange (unsigned_type_node, UINT(0), UINT(5), irange::PLAIN); + r0.invert (); + ASSERT_TRUE (r0 == irange (unsigned_type_node, UINT(6), maxuint)); + + /* Check that ~[10,MAX] => [0,9] for unsigned int. */ + r0 = irange (unsigned_type_node, UINT(10), maxuint, irange::PLAIN); + r0.invert (); + ASSERT_TRUE (r0 == irange (unsigned_type_node, UINT(0), UINT(9))); + + /* Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. */ + r0.set_range (u128_type, UINT128(0), UINT128(5), irange::INVERSE); + r1 = irange (u128_type, UINT128(6), build_minus_one_cst (u128_type)); + ASSERT_TRUE (r0 == r1); + + /* Check that [~5] is really [-MIN,4][6,MAX]. */ + r0 = irange (integer_type_node, INT(5), INT(5), irange::INVERSE); + r1 = irange (integer_type_node, minint, INT(4)); + ASSERT_TRUE (r1.union_ (irange (integer_type_node, + INT(6), maxint))); + + ASSERT_TRUE (r0 == r1); + + r1.set_range (integer_type_node, INT(5), INT(5)); + ASSERT_TRUE (r1.valid_p ()); + irange r2 (r1); + ASSERT_TRUE (r1 == r2); + + r1 = RANGE1 (5, 10); + ASSERT_TRUE (r1.valid_p ()); + + r1 = irange (integer_type_node, (wide_int) INT(5), (wide_int) INT(10)); + ASSERT_TRUE (r1.valid_p ()); + ASSERT_TRUE (r1.contains_p (INT (7))); + + r1 = irange (signed_char_type_node, SCHAR(0), SCHAR(20)); + ASSERT_TRUE (r1.contains_p (INT(15))); + ASSERT_FALSE (r1.contains_p (INT(300))); + + /* If a range is in any way outside of the range for the converted + to range, default to the range for the new type. */ + r1 = irange (integer_type_node, integer_zero_node, maxint); + r1.cast (short_integer_type_node); + ASSERT_TRUE (r1.lower_bound () == minshort && r1.upper_bound() == maxshort); + + /* (unsigned char)[-5,-1] => [251,255]. */ + r0 = rold = irange (signed_char_type_node, SCHAR (-5), SCHAR(-1)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (unsigned_char_type_node, + UCHAR(251), UCHAR(255))); + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == rold); + + /* (signed char)[15, 150] => [-128,-106][15,127]. */ + r0 = rold = irange (unsigned_char_type_node, UCHAR(15), UCHAR(150)); + r0.cast (signed_char_type_node); + r1 = irange (signed_char_type_node, SCHAR(15), SCHAR(127)); + r2 = irange (signed_char_type_node, SCHAR(-128), SCHAR(-106)); + r1.union_ (r2); + ASSERT_TRUE (r1 == r0); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == rold); + + /* (unsigned char)[-5, 5] => [0,5][251,255]. */ + r0 = rold = irange (signed_char_type_node, SCHAR(-5), SCHAR(5)); + r0.cast (unsigned_char_type_node); + r1 = irange (unsigned_char_type_node, UCHAR(251), UCHAR(255)); + r2 = irange (unsigned_char_type_node, UCHAR(0), UCHAR(5)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == rold); + + /* (unsigned char)[-5,5] => [0,255]. */ + r0 = irange (integer_type_node, INT(-5), INT(5)); + r0.cast (unsigned_char_type_node); + r1 = irange (unsigned_char_type_node, + TYPE_MIN_VALUE (unsigned_char_type_node), + TYPE_MAX_VALUE (unsigned_char_type_node)); + ASSERT_TRUE (r0 == r1); + + /* (unsigned char)[5U,1974U] => [0,255]. */ + r0 = irange (unsigned_type_node, UINT(5), UINT(1974)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (unsigned_char_type_node, UCHAR(0), UCHAR(255))); + r0.cast (integer_type_node); + /* Going to a wider range should not sign extend. */ + ASSERT_TRUE (r0 == RANGE1 (0, 255)); + + /* (unsigned char)[-350,15] => [0,255]. */ + r0 = irange (integer_type_node, INT(-350), INT(15)); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == irange (unsigned_char_type_node, + TYPE_MIN_VALUE (unsigned_char_type_node), + TYPE_MAX_VALUE (unsigned_char_type_node))); + + /* Casting [-120,20] from signed char to unsigned short. + (unsigned)[(signed char)-120, (signed char)20] + => (unsigned)[0, 0x14][0x88, 0xff] + => [0,0x14][0xff88,0xffff]. */ + r0 = irange (signed_char_type_node, SCHAR(-120), SCHAR(20)); + r0.cast (short_unsigned_type_node); + r1 = irange (short_unsigned_type_node, UINT16(0), UINT16(0x14)); + r2 = irange (short_unsigned_type_node, UINT16(0xff88), UINT16(0xffff)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + /* Casting back to signed char (a smaller type), would be outside of + the range, we it'll be the entire range of the signed char. */ + r0.cast (signed_char_type_node); + ASSERT_TRUE (r0 == irange (signed_char_type_node, + TYPE_MIN_VALUE (signed_char_type_node), + TYPE_MAX_VALUE (signed_char_type_node))); + + /* unsigned char -> signed short + (signed short)[(unsigned char)25, (unsigned char)250] + => [(signed short)25, (signed short)250]. */ + r0 = rold = irange (unsigned_char_type_node, UCHAR(25), UCHAR(250)); + r0.cast (short_integer_type_node); + r1 = irange (short_integer_type_node, INT16(25), INT16(250)); + ASSERT_TRUE (r0 == r1); + r0.cast (unsigned_char_type_node); + ASSERT_TRUE (r0 == rold); + + /* Test casting a wider signed [-MIN,MAX] to a narrower unsigned. */ + r0 = irange (long_long_integer_type_node, + TYPE_MIN_VALUE (long_long_integer_type_node), + TYPE_MAX_VALUE (long_long_integer_type_node)); + r0.cast (short_unsigned_type_node); + r1 = irange (short_unsigned_type_node, + TYPE_MIN_VALUE (short_unsigned_type_node), + TYPE_MAX_VALUE (short_unsigned_type_node)); + ASSERT_TRUE (r0 == r1); + + /* Test that casting a range with MAX_PAIRS that changes sign is + done conservatively. + + (unsigned short)[-5,5][20,30][40,50]... + => (unsigned short)[-5,50] + => [0,50][65531,65535]. */ + r0 = irange (short_integer_type_node, INT16(-5), INT16(5)); + gcc_assert (r0.max_pairs * 2 * 10 + 10 < 32767); + unsigned i; + for (i = 2; i < r0.max_pairs * 2; i += 2) + { + r1 = irange (short_integer_type_node, INT16(i * 10), INT16(i * 10 + 10)); + r0.union_ (r1); + } + r0.cast(short_unsigned_type_node); + r1 = irange (short_unsigned_type_node, INT16(0), INT16((i - 2) * 10 + 10)); + r2 = irange (short_unsigned_type_node, INT16(65531), INT16(65535)); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + + /* NOT([10,20]) ==> [-MIN,9][21,MAX]. */ + r0 = r1 = irange (integer_type_node, INT(10), INT(20)); + r2 = irange (integer_type_node, minint, INT(9)); + ASSERT_TRUE (r2.union_ (irange (integer_type_node, + INT(21), maxint))); + r1.invert (); + ASSERT_TRUE (r1 == r2); + /* Test that NOT(NOT(x)) == x. */ + r2.invert (); + ASSERT_TRUE (r0 == r2); + + /* NOT(-MIN,+MAX) is the empty set and should return false. */ + r0 = irange (integer_type_node, wide_int_to_tree (integer_type_node, minint), + wide_int_to_tree (integer_type_node, maxint)); + ASSERT_TRUE (!r0.invert ()); + r1.clear (); + ASSERT_TRUE (r0 == r1); + + /* Test that booleans and their inverse work as expected. */ + range_zero (&r0, boolean_type_node); + ASSERT_TRUE (r0 == irange (boolean_type_node, + build_int_cst (boolean_type_node, 0), + build_int_cst (boolean_type_node, 0))); + r0.invert(); + ASSERT_TRUE (r0 == irange (boolean_type_node, + build_int_cst (boolean_type_node, 1), + build_int_cst (boolean_type_node, 1))); + + /* Casting NONZERO to a narrower type will wrap/overflow so + it's just the entire range for the narrower type. + + "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is + is outside of the range of a smaller range, return the full + smaller range. */ + range_non_zero (&r0, integer_type_node); + r0.cast (short_integer_type_node); + r1 = irange (short_integer_type_node, + TYPE_MIN_VALUE (short_integer_type_node), + TYPE_MAX_VALUE (short_integer_type_node)); + ASSERT_TRUE (r0 == r1); + + /* Casting NONZERO from a narrower signed to a wider signed. + + NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16]. + Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. */ + range_non_zero (&r0, short_integer_type_node); + r0.cast (integer_type_node); + r1 = RANGE1 (-32768, -1); + r2 = RANGE1 (1, 32767); + r1.union_ (r2); + ASSERT_TRUE (r0 == r1); + + if (irange::max_pairs > 2) + { + /* ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]. */ + r0 = RANGE1 (10, 20); + r1 = RANGE1 (5, 8); + r0.union_ (r1); + r1 = RANGE1 (1, 3); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20)); + + /* [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]. */ + r1 = irange (integer_type_node, INT(-5), INT(0)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20)); + } + + /* [10,20] U [30,40] ==> [10,20][30,40]. */ + r0 = irange (integer_type_node, INT(10), INT(20)); + r1 = irange (integer_type_node, INT(30), INT(40)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (10, 20, 30, 40)); + if (irange::max_pairs > 2) + { + /* [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]. */ + r1 = irange (integer_type_node, INT(50), INT(60)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60)); + /* [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,80]. */ + r1 = irange (integer_type_node, INT(70), INT(80)); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 80)); + } + + /* Make sure NULL and non-NULL of pointer types work, and that + inverses of them are consistent. */ + tree voidp = build_pointer_type (void_type_node); + range_zero (&r0, voidp); + r1 = r0; + r0.invert (); + r0.invert (); + ASSERT_TRUE (r0 == r1); + + if (irange::max_pairs > 2) + { + /* [10,20][30,40][50,60] U [6,35] => [6,40][50,60]. */ + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = RANGE1 (6, 35); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (6,40,50,60)); + + /* [10,20][30,40][50,60] U [6,60] => [6,60] */ + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = RANGE1 (6, 60); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (6,60)); + + /* [10,20][30,40][50,60] U [6,70] => [6,70]. */ + r0 = RANGE3 (10, 20, 30, 40, 50, 60); + r1 = RANGE1 (6, 70); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (6,70)); + + /* [10,20][30,40][50,60] U [35,70] => [10,20][30,70]. */ + r0 = RANGE3 (10,20,30,40,50,60); + r1 = RANGE1 (35,70); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (10,20,30,70)); + } + + /* [10,20][30,40] U [25,70] => [10,70]. */ + r0 = RANGE2 (10,20,30,40); + r1 = RANGE1 (25,70); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (10,20,30,70)); + + if (irange::max_pairs > 2) + { + /* [10,20][30,40][50,60] U [15,35] => [10,40][50,60]. */ + r0 = RANGE3 (10,20,30,40,50,60); + r1 = RANGE1 (15,35); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (10,40,50,60)); + } + + /* [10,20] U [15, 30] => [10, 30]. */ + r0 = RANGE1 (10,20); + r1 = RANGE1 (15,30); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (10,30)); + + /* [10,20] U [25,25] => [10,20][25,25]. */ + r0 = RANGE1 (10,20); + r1 = RANGE1 (25,25); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE2 (10,20,25,25)); + + if (irange::max_pairs > 2) + { + /* [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]. */ + r0 = RANGE3 (10,20,30,40,50,60); + r1 = RANGE1 (35,35); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE3 (10,20,30,40,50,60)); + } + + /* [15,40] U [] => [15,40]. */ + r0 = RANGE1 (15,40); + r1.clear (); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (15,40)); + + /* [10,20] U [10,10] => [10,20]. */ + r0 = RANGE1 (10,20); + r1 = RANGE1 (10,10); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (10,20)); + + /* [10,20] U [9,9] => [9,20]. */ + r0 = RANGE1 (10,20); + r1 = RANGE1 (9,9); + r0.union_ (r1); + ASSERT_TRUE (r0 == RANGE1 (9,20)); + + if (irange::max_pairs > 2) + { + /* [10,10][12,12][20,100] ^ [15,200]. */ + r0 = RANGE3 (10,10,12,12,20,100); + r1 = RANGE1 (15,200); + r0.intersect (r1); + ASSERT_TRUE (r0 == RANGE1 (20,100)); + + /* [10,20][30,40][50,60] ^ [15,25][38,51][55,70] + => [15,20][38,40][50,60]. */ + r0 = RANGE3 (10,20,30,40,50,60); + r1 = RANGE3 (15,25,38,51,55,70); + r0.intersect (r1); + ASSERT_TRUE (r0 == RANGE3 (15,20,38,40,50,60)); + + /* [15,20][30,40][50,60] ^ [15,35][40,90][100,200] + => [15,20][30,35][40,60]. */ + r0 = RANGE3 (15,20,30,40,50,60); + r1 = RANGE3 (15,35,40,90,100,200); + r0.intersect (r1); + ASSERT_TRUE (r0 == RANGE3 (15,20,30,35,40,60)); + } + + /* [10,20] ^ [15,30] => [15,20]. */ + r0 = RANGE1 (10, 20); + r1 = RANGE1 (15, 30); + r0.intersect (r1); + ASSERT_TRUE (r0 == RANGE1 (15, 20)); + + /* [10,20][30,40] ^ [40,50] => [40,40]. */ + r0 = RANGE2 (10,20,30,40); + r1 = RANGE1 (40,50); + r0.intersect (r1); + ASSERT_TRUE (r0 == RANGE1 (40,40)); + + /* Test non-destructive intersection. */ + r0 = rold = RANGE1 (10, 20); + ASSERT_TRUE (irange_intersect (r0, RANGE1 (15, 30))); + ASSERT_TRUE (r0 == rold); +} + +} // namespace selftest +#endif // CHECKING_P diff --git a/gcc/range.h b/gcc/range.h new file mode 100644 index 0000000..158c980 --- /dev/null +++ b/gcc/range.h @@ -0,0 +1,230 @@ +/* Header file for range analysis. + Copyright (C) 2017 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_RANGE_H +#define GCC_RANGE_H + +class irange_storage; + +/* This is a class for working with ranges, currently integer ones. + With it you can specify a range of [5,10] (5 through 10 inclusive), + or even ranges including multi-part ranges [-10,5][30,40][50,60]. + This last one specifies the union of the different sub-ranges. + + Inverse ranges are represented as an actual range. For instance, + the inverse of 0 is [-MIN,-1][1,+MAX] for a signed integer. + + Methods are provided for intersecting and uniting ranges, as well + as converting between them. In performing any of these operations, + when no efficient way can be computed, we may default to a more + conservative range. + + For example, the inverse of [5,10][15,20][30,40] is actually + [-MIN,4][11,14][21,29][41,+MAX]. If this cannot be efficiently or + quickly computed, we may opt to represent the inverse as + [-MIN,4][41,+MAX] which is an equivalent conservative + representation. + + This class is not meant to live in long term storage (GC). + Consequently, there are no GTY markers. For long term storage, use + the irange_storage class described later. */ +class irange +{ + friend class irange_storage; + public: + /* Maximum number of pairs of ranges allowed. */ + static const unsigned int max_pairs = 2; + + private: + /* Number of items in bounds[]. */ + unsigned char nitems; + /* Whether or not a set operation overflowed. */ + bool overflow; + /* The type of the range. */ + const_tree type; + /* The pairs of sub-ranges in the range. */ + wide_int bounds[max_pairs * 2]; + + void prepend (const wide_int &x, const wide_int &y); + void append (const wide_int &x, const wide_int &y); + void remove (unsigned i, unsigned j); + void canonicalize (); + + public: + /* When constructing a range, this specifies wether this is a + regular range, or the inverse of a range. */ + enum kind { PLAIN, INVERSE }; + irange () { type = NULL_TREE; nitems = 0; } + explicit irange (const_tree t) { set_range (t); } + irange (const_tree typ, const wide_int &lbound, const wide_int &ubound, + kind rt = PLAIN) + { set_range (typ, lbound, ubound, rt); } + irange (const irange &); + irange (const irange_storage *stor, tree typ) { set_range (stor, typ); } + + void set_range (const irange_storage *, const_tree); + void set_range (const_tree); + void set_range (const_tree, const wide_int &lbound, const wide_int &ubound, + kind rt = PLAIN); + void set_range_for_type (const_tree); + + bool overflow_p () const { return overflow && !TYPE_OVERFLOW_WRAPS (type); } + void set_overflow () { overflow = true; } + void clear_overflow () { overflow = false; } + + unsigned num_pairs () const { return nitems / 2; } + /* Implicit conversion to `unsigned int' returns the number of pairs. */ + operator unsigned () const { return num_pairs (); } + /* Returns the lower bound of PAIR. */ + wide_int lower_bound (unsigned pair = 0) const + { + gcc_assert (nitems != 0 && pair <= num_pairs ()); + return bounds[pair * 2]; + } + /* Returns the uppermost bound. */ + wide_int upper_bound () const + { + gcc_assert (nitems != 0); + return bounds[nitems - 1]; + } + wide_int upper_bound (unsigned pair) const; + + /* Remove a sub-range from a range. PAIR is the zero-based + sub-range to remove. */ + void remove_pair (unsigned pair) { remove (pair * 2, pair * 2 + 1); } + void clear () { nitems = 0; } + void clear (const_tree t) { type = t; nitems = 0; overflow = false; } + bool empty_p () const { return !nitems; } + bool range_for_type_p () const; + bool simple_range_p () const { return nitems == 2; } + + void dump (); + void dump (pretty_printer *pp); + void dump (FILE *); + + bool valid_p () const; + void cast (const_tree type); + bool contains_p (const wide_int &element) const; + bool contains_p (const_tree) const; + + const_tree get_type () const { return type; } + + irange& operator= (const irange &r); + irange& operator= (const_tree t); + + bool operator== (const irange &r) const; + bool operator!= (const irange &r) const { return !(*this == r); } + + irange &union_ (const wide_int &x, const wide_int &y); + irange &union_ (const irange &r); + irange &intersect (const wide_int &x, const wide_int &y); + irange &intersect (const irange &r); + irange &invert (); +}; + +/* Return R1 U R2. */ +static inline +irange &irange_union (const irange &r1, const irange &r2) +{ + return irange (r1).union_ (r2); +} + +/* Return R1 ^ R2. */ +static inline +irange &irange_intersect (const irange &r1, const irange &r2) +{ + return irange (r1).intersect (r2); +} + +/* Return the inverse range of R1. */ +static inline +irange &irange_invert (const irange &r1) +{ + return irange (r1).invert (); +} + +void range_zero (irange *r, tree type); +void range_one (irange *r, tree type); +bool range_non_zero (irange *r, tree type); +void range_positives (irange *r, tree type, unsigned int); + +/* An irange is inefficient when it comes to memory, so this class is + used to store iranges in memory (off of an SSA_NAME likely). It is + a variable length structure that contains the sub-range pairs as + well as the non-zero bitmask. The number of entries are + irnage::max_pairs * 2 + 1 (to accomodate the non-zero bits). + + To store an irange class X into this memory efficient irange_storage + class use: + + irange X; + ... + irange_storage *stow = irange_storage::ggc_alloc (precision); + stow->set_irange (X); + + To convert it back to an irange use: + + tree type = ...; + irange X (stow, type); + or + if (SSA_NAME_RANGE_INFO (ssa)) { + irange X (ssa); + ... + } + + To get at the nonzero bits use: + + irange_storage *stow = ...; + stow->set_nonzero_bits(); + stow->get_nonzero_bits(); +*/ + +class GTY((variable_size)) irange_storage +{ + friend class irange; + public: + /* These are the pair of subranges for the irange. The last + wide_int allocated is a mask representing which bits in an + integer are known to be non-zero. */ + trailing_wide_ints trailing_bounds; + + void set_irange (const irange &); + /* Returns the size of an irange_storage with PRECISION. */ + static size_t size (unsigned precision) + { return sizeof (irange_storage) + /* There is a +1 for the non-zero bits field. */ + + trailing_wide_ints::extra_size (precision); + } + /* Allocate GC memory for an irange_storage with PRECISION. */ + static irange_storage *ggc_alloc (unsigned precision) + { irange_storage *stow = static_cast (ggc_internal_alloc + (size (precision))); + stow->trailing_bounds.set_precision (precision); + return stow; + } + /* Set the nonzero bit mask to WI. */ + void set_nonzero_bits (const wide_int &wi) + { trailing_bounds[irange::max_pairs * 2] = wi; } + /* Return the nonzero bits in the range. */ + wide_int get_nonzero_bits (void) + { return trailing_bounds[irange::max_pairs * 2]; } +}; + +#endif // GCC_RANGE_H diff --git a/gcc/selftest.h b/gcc/selftest.h index dad53e9..e15cb07 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -196,6 +196,7 @@ extern void tree_c_tests (); extern void tree_cfg_c_tests (); extern void vec_c_tests (); extern void wide_int_cc_tests (); +extern void irange_tests (); extern int num_passes; diff --git a/gcc/ssa.h b/gcc/ssa.h index 4bc6b3f..f84d6e8 100644 --- a/gcc/ssa.h +++ b/gcc/ssa.h @@ -26,6 +26,7 @@ along with GCC; see the file COPYING3. If not see #include "stringpool.h" #include "gimple-ssa.h" #include "tree-vrp.h" +#include "range.h" #include "tree-ssanames.h" #include "tree-phinodes.h" #include "ssa-iterators.h" diff --git a/gcc/tree-core.h b/gcc/tree-core.h index ea73477..d9a708d 100644 --- a/gcc/tree-core.h +++ b/gcc/tree-core.h @@ -33,7 +33,7 @@ struct function; struct real_value; struct fixed_value; struct ptr_info_def; -struct range_info_def; +class irange_storage; struct die_struct; @@ -1043,9 +1043,6 @@ struct GTY(()) tree_base { TRANSACTION_EXPR_OUTER in TRANSACTION_EXPR - SSA_NAME_ANTI_RANGE_P in - SSA_NAME - MUST_TAIL_CALL in CALL_EXPR @@ -1403,6 +1400,7 @@ struct GTY(()) ssa_use_operand_t { tree *GTY((skip(""))) use; }; +class irange; struct GTY(()) tree_ssa_name { struct tree_typed typed; @@ -1416,8 +1414,8 @@ struct GTY(()) tree_ssa_name { union ssa_name_info_type { /* Pointer attributes used for alias analysis. */ struct GTY ((tag ("0"))) ptr_info_def *ptr_info; - /* Value range attributes used for zero/sign extension elimination. */ - struct GTY ((tag ("1"))) range_info_def *range_info; + /* Value range attributes. */ + class GTY ((tag ("1"))) irange_storage *range_info; } GTY ((desc ("%1.typed.type ?" \ "!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info; diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 95f65b0..f218d05 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -3332,7 +3332,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) base_min = base_max = base; else if (TREE_CODE (base) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (base)) - && get_range_info (base, &base_min, &base_max) == VR_RANGE) + && get_range_info (base, &base_min, &base_max)) ; else return true; @@ -3341,7 +3341,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) step_min = step_max = step; else if (TREE_CODE (step) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (step)) - && get_range_info (step, &step_min, &step_max) == VR_RANGE) + && get_range_info (step, &step_min, &step_max)) ; else return true; diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 9f0fe54..dd4f26d 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -545,8 +545,8 @@ fini_copy_prop (void) && !SSA_NAME_RANGE_INFO (copy_of[i].value) && var_bb == copy_of_bb) duplicate_ssa_name_range_info (copy_of[i].value, - SSA_NAME_RANGE_TYPE (var), - SSA_NAME_RANGE_INFO (var)); + SSA_NAME_RANGE_INFO (var), + TREE_TYPE (var)); } } diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index e67cd93..67d017a 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -225,7 +225,7 @@ refine_value_range_using_guard (tree type, tree var, } else if (TREE_CODE (varc1) == SSA_NAME && INTEGRAL_TYPE_P (type) - && get_range_info (varc1, &minv, &maxv) == VR_RANGE) + && get_range_info (varc1, &minv, &maxv)) { gcc_assert (wi::le_p (minv, maxv, sgn)); wi::to_mpz (minv, minc1, sgn); @@ -347,8 +347,6 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, int cnt = 0; mpz_t minm, maxm; basic_block bb; - wide_int minv, maxv; - enum value_range_type rtype = VR_VARYING; /* If the expression is a constant, we know its value exactly. */ if (integer_zerop (var)) @@ -368,7 +366,8 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi_iterator gsi; /* Either for VAR itself... */ - rtype = get_range_info (var, &minv, &maxv); + wide_int minv, maxv; + bool have_range = get_range_info (var, &minv, &maxv); /* Or for PHI results in loop->header where VAR is used as PHI argument from the loop preheader edge. */ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -376,12 +375,11 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi *phi = gsi.phi (); wide_int minc, maxc; if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var - && (get_range_info (gimple_phi_result (phi), &minc, &maxc) - == VR_RANGE)) + && get_range_info (gimple_phi_result (phi), &minc, &maxc)) { - if (rtype != VR_RANGE) + if (!have_range) { - rtype = VR_RANGE; + have_range = true; minv = minc; maxv = maxc; } @@ -395,7 +393,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, involved. */ if (wi::gt_p (minv, maxv, sgn)) { - rtype = get_range_info (var, &minv, &maxv); + have_range = get_range_info (var, &minv, &maxv); break; } } @@ -403,17 +401,17 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, } mpz_init (minm); mpz_init (maxm); - if (rtype != VR_RANGE) - { - mpz_set (minm, min); - mpz_set (maxm, max); - } - else + if (have_range) { gcc_assert (wi::le_p (minv, maxv, sgn)); wi::to_mpz (minv, minm, sgn); wi::to_mpz (maxv, maxm, sgn); } + else + { + mpz_set (minm, min); + mpz_set (maxm, max); + } /* Now walk the dominators of the loop header and use the entry guards to refine the estimates. */ for (bb = loop->header; @@ -3140,7 +3138,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (high) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && (get_range_info (orig_base, &min, &max) == VR_RANGE + && (get_range_info (orig_base, &min, &max) || get_cst_init_from_scev (orig_base, &max, false)) && wi::gts_p (high, max)) base = wide_int_to_tree (unsigned_type, max); @@ -3158,7 +3156,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (low) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && (get_range_info (orig_base, &min, &max) == VR_RANGE + && (get_range_info (orig_base, &min, &max) || get_cst_init_from_scev (orig_base, &min, true)) && wi::gts_p (min, low)) base = wide_int_to_tree (unsigned_type, min); @@ -4397,7 +4395,6 @@ scev_var_range_cant_overflow (tree var, tree step, struct loop *loop) { tree type; wide_int minv, maxv, diff, step_wi; - enum value_range_type rtype; if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var))) return false; @@ -4408,8 +4405,7 @@ scev_var_range_cant_overflow (tree var, tree step, struct loop *loop) if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb)) return false; - rtype = get_range_info (var, &minv, &maxv); - if (rtype != VR_RANGE) + if (!get_range_info (var, &minv, &maxv)) return false; /* VAR is a scev whose evolution part is STEP and value range info diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index b652361..f06985b 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -1065,11 +1065,11 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, SSA_NAME_RANGE_INFO (lhs) = NULL; /* If available, we can use VR of phi result at least. */ tree phires = gimple_phi_result (phi); - struct range_info_def *phires_range_info + irange_storage *phires_range_info = SSA_NAME_RANGE_INFO (phires); if (phires_range_info) - duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires), - phires_range_info); + duplicate_ssa_name_range_info (lhs, phires_range_info, + TREE_TYPE (phires)); } gimple_stmt_iterator gsi_from = gsi_for_stmt (assign); gsi_move_before (&gsi_from, &gsi); diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 2a431c9..e69cbc1 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -3107,12 +3107,11 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, && SSA_NAME_RANGE_INFO (expr->u.nary->op[0])) { wide_int min, max; - if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE + if (get_range_info (expr->u.nary->op[0], &min, &max) && !wi::neg_p (min, SIGNED) && !wi::neg_p (max, SIGNED)) /* Just handle extension and sign-changes of all-positive ranges. */ - set_range_info (temp, - SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]), + set_range_info (temp, VR_RANGE, wide_int_storage::from (min, TYPE_PRECISION (type), TYPE_SIGN (type)), wide_int_storage::from (max, TYPE_PRECISION (type), @@ -4326,8 +4325,8 @@ eliminate_dom_walker::before_dom_children (basic_block b) && ! VN_INFO_RANGE_INFO (sprime) && b == sprime_b) duplicate_ssa_name_range_info (sprime, - VN_INFO_RANGE_TYPE (lhs), - VN_INFO_RANGE_INFO (lhs)); + VN_INFO_RANGE_INFO (lhs), + TREE_TYPE (lhs)); } /* Inhibit the use of an inserted PHI on a loop header when diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index c140c35..a991735 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -3349,24 +3349,15 @@ set_ssa_val_to (tree from, tree to) { /* Save old info. */ if (! VN_INFO (to)->info.range_info) - { - VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to); - VN_INFO (to)->range_info_anti_range_p - = SSA_NAME_ANTI_RANGE_P (to); - } + VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to); /* Use that from the dominator. */ SSA_NAME_RANGE_INFO (to) = SSA_NAME_RANGE_INFO (from); - SSA_NAME_ANTI_RANGE_P (to) = SSA_NAME_ANTI_RANGE_P (from); } else { /* Save old info. */ if (! VN_INFO (to)->info.range_info) - { - VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to); - VN_INFO (to)->range_info_anti_range_p - = SSA_NAME_ANTI_RANGE_P (to); - } + VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to); /* Rather than allocating memory and unioning the info just clear it. */ SSA_NAME_RANGE_INFO (to) = NULL; @@ -4616,11 +4607,7 @@ scc_vn_restore_ssa_info (void) SSA_NAME_PTR_INFO (name) = VN_INFO (name)->info.ptr_info; else if (INTEGRAL_TYPE_P (TREE_TYPE (name)) && VN_INFO (name)->info.range_info) - { - SSA_NAME_RANGE_INFO (name) = VN_INFO (name)->info.range_info; - SSA_NAME_ANTI_RANGE_P (name) - = VN_INFO (name)->range_info_anti_range_p; - } + SSA_NAME_RANGE_INFO (name) = VN_INFO (name)->info.range_info; } } } diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h index 77d0183..6ad8e53 100644 --- a/gcc/tree-ssa-sccvn.h +++ b/gcc/tree-ssa-sccvn.h @@ -201,9 +201,6 @@ typedef struct vn_ssa_aux insertion of such with EXPR as definition is required before a use can be created of it. */ unsigned needs_insertion : 1; - - /* Whether range-info is anti-range. */ - unsigned range_info_anti_range_p : 1; } *vn_ssa_aux_t; enum vn_lookup_kind { VN_NOWALK, VN_WALK, VN_WALKREWRITE }; @@ -262,7 +259,7 @@ vn_valueize (tree name) /* Get at the original range info for NAME. */ -inline range_info_def * +inline irange_storage * VN_INFO_RANGE_INFO (tree name) { return (VN_INFO (name)->info.range_info @@ -270,24 +267,6 @@ VN_INFO_RANGE_INFO (tree name) : SSA_NAME_RANGE_INFO (name)); } -/* Whether the original range info of NAME is an anti-range. */ - -inline bool -VN_INFO_ANTI_RANGE_P (tree name) -{ - return (VN_INFO (name)->info.range_info - ? VN_INFO (name)->range_info_anti_range_p - : SSA_NAME_ANTI_RANGE_P (name)); -} - -/* Get at the original range info kind for NAME. */ - -inline value_range_type -VN_INFO_RANGE_TYPE (tree name) -{ - return VN_INFO_ANTI_RANGE_P (name) ? VR_ANTI_RANGE : VR_RANGE; -} - /* Get at the original pointer info for NAME. */ inline ptr_info_def * diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 353c7b1..cf6c8c6 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -328,59 +328,57 @@ set_range_info (tree name, enum value_range_type range_type, { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); - range_info_def *ri = SSA_NAME_RANGE_INFO (name); + irange_storage *ri = SSA_NAME_RANGE_INFO (name); unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); /* Allocate if not available. */ if (ri == NULL) { - size_t size = (sizeof (range_info_def) - + trailing_wide_ints <3>::extra_size (precision)); - ri = static_cast (ggc_internal_alloc (size)); - ri->ints.set_precision (precision); + ri = irange_storage::ggc_alloc (precision); SSA_NAME_RANGE_INFO (name) = ri; ri->set_nonzero_bits (wi::shwi (-1, precision)); } - /* Record the range type. */ - if (SSA_NAME_RANGE_TYPE (name) != range_type) - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); - - /* Set the values. */ - ri->set_min (min); - ri->set_max (max); + signop sign = TYPE_SIGN (TREE_TYPE (name)); + irange local (TREE_TYPE (name), + wide_int_storage::from (min, precision, sign), + wide_int_storage::from (max, precision, sign), + range_type == VR_ANTI_RANGE ? irange::INVERSE : irange::PLAIN); + ri->set_irange (local); /* If it is a range, try to improve nonzero_bits from the min/max. */ if (range_type == VR_RANGE) { - wide_int xorv = ri->get_min () ^ ri->get_max (); + wide_int xorv = min ^ max; if (xorv != 0) xorv = wi::mask (precision - wi::clz (xorv), false, precision); - ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv)); + ri->set_nonzero_bits (ri->get_nonzero_bits () & (min | xorv)); } } -/* Gets range information MIN, MAX and returns enum value_range_type - corresponding to tree ssa_name NAME. enum value_range_type returned - is used to determine if MIN and MAX are valid values. */ +/* If there is range information available for the given ssa_name + NAME, returns TRUE and sets MIN, MAX accordingly. */ -enum value_range_type +bool get_range_info (const_tree name, wide_int *min, wide_int *max) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); - range_info_def *ri = SSA_NAME_RANGE_INFO (name); /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */ - if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) - > 2 * HOST_BITS_PER_WIDE_INT)) - return VR_VARYING; + if (!SSA_NAME_RANGE_INFO (name) + // FIXME: ?? Do we need this precision stuff ?? + || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) + > 2 * HOST_BITS_PER_WIDE_INT)) + return false; - *min = ri->get_min (); - *max = ri->get_max (); - return SSA_NAME_RANGE_TYPE (name); + irange ri (name); + gcc_assert (ri.valid_p ()); + *min = ri.lower_bound (); + *max = ri.upper_bound (); + return true; } /* Set nonnull attribute to pointer NAME. */ @@ -415,14 +413,14 @@ get_ptr_nonnull (const_tree name) /* Change non-zero bits bitmask of NAME. */ void -set_nonzero_bits (tree name, const wide_int_ref &mask) +set_nonzero_bits (tree name, const wide_int &mask) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); if (SSA_NAME_RANGE_INFO (name) == NULL) set_range_info (name, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (name)), TYPE_MAX_VALUE (TREE_TYPE (name))); - range_info_def *ri = SSA_NAME_RANGE_INFO (name); + irange_storage *ri = SSA_NAME_RANGE_INFO (name); ri->set_nonzero_bits (mask); } @@ -442,7 +440,7 @@ get_nonzero_bits (const_tree name) return wi::shwi (-1, precision); } - range_info_def *ri = SSA_NAME_RANGE_INFO (name); + irange_storage *ri = SSA_NAME_RANGE_INFO (name); if (!ri) return wi::shwi (-1, precision); @@ -676,29 +674,38 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) SSA_NAME_PTR_INFO (name) = new_ptr_info; } -/* Creates a duplicate of the range_info_def at RANGE_INFO of type - RANGE_TYPE for use by the SSA name NAME. */ +/* Creates a duplicate of the range info at OLD_RANGE_INFO for use by the + SSA name NAME. */ void -duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, - struct range_info_def *range_info) +duplicate_ssa_name_range_info (tree name, irange_storage *old_range_info, + tree old_type) { - struct range_info_def *new_range_info; - gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (!SSA_NAME_RANGE_INFO (name)); - if (!range_info) + if (!old_range_info) return; unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); - size_t size = (sizeof (range_info_def) - + trailing_wide_ints <3>::extra_size (precision)); - new_range_info = static_cast (ggc_internal_alloc (size)); - memcpy (new_range_info, range_info, size); - - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); + irange_storage *new_range_info = irange_storage::ggc_alloc (precision); SSA_NAME_RANGE_INFO (name) = new_range_info; + /* If NAME was created with copy_ssa_name_fn(), we may have gotten + the TYPE_MAIN_VARIANT for the original type, which may be a + different typedef of the original type. If so, convert the range + to be consistent. + + NOTE: I have also seen tree-ssa-pre.c copy the range of an + 'unsigned long long' onto the range of a 'unsigned long'. So the + two types are not necessarily of the same size. */ + if (TREE_TYPE (name) != old_type) + { + irange ir (old_range_info, old_type); + ir.cast (TREE_TYPE (name)); + new_range_info->set_irange (ir); + new_range_info->set_nonzero_bits (old_range_info->get_nonzero_bits ()); + return; + } + memcpy (new_range_info, old_range_info, irange_storage::size (precision)); } @@ -719,11 +726,11 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt) } else { - struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); + irange_storage *old_range_info = SSA_NAME_RANGE_INFO (name); if (old_range_info) - duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), - old_range_info); + duplicate_ssa_name_range_info (new_name, + old_range_info, TREE_TYPE (name)); } return new_name; diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index 9a18394..ab1cfe7 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -45,14 +45,12 @@ struct GTY(()) ptr_info_def unsigned int misalign; }; -/* Value range information for SSA_NAMEs representing non-pointer variables. */ - -struct GTY ((variable_size)) range_info_def { - /* Minimum, maximum and nonzero bits. */ - TRAILING_WIDE_INT_ACCESSOR (min, ints, 0) - TRAILING_WIDE_INT_ACCESSOR (max, ints, 1) - TRAILING_WIDE_INT_ACCESSOR (nonzero_bits, ints, 2) - trailing_wide_ints <3> ints; +/* Used bits information for SSA_NAMEs representing non-pointer variables. */ + +struct GTY ((variable_size)) nonzero_bits_def { + /* Mask representing which bits are known to be used in an integer. */ + TRAILING_WIDE_INT_ACCESSOR (nonzero_bits, ints, 0) + trailing_wide_ints <1> ints; }; @@ -70,9 +68,8 @@ struct GTY ((variable_size)) range_info_def { extern void set_range_info (tree, enum value_range_type, const wide_int_ref &, const wide_int_ref &); /* Gets the value range from SSA. */ -extern enum value_range_type get_range_info (const_tree, wide_int *, - wide_int *); -extern void set_nonzero_bits (tree, const wide_int_ref &); +extern bool get_range_info (const_tree, wide_int *, wide_int *); +extern void set_nonzero_bits (tree, const wide_int &); extern wide_int get_nonzero_bits (const_tree); extern bool ssa_name_has_boolean_range (tree); extern void init_ssanames (struct function *, int); @@ -95,8 +92,7 @@ extern bool get_ptr_nonnull (const_tree); extern tree copy_ssa_name_fn (struct function *, tree, gimple *); extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *); extern tree duplicate_ssa_name_fn (struct function *, tree, gimple *); -extern void duplicate_ssa_name_range_info (tree, enum value_range_type, - struct range_info_def *); +extern void duplicate_ssa_name_range_info (tree, irange_storage *, tree); extern void reset_flow_sensitive_info (tree); extern void reset_flow_sensitive_info_in_bb (basic_block); extern void release_defs (gimple *); diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index 39f0133..05bf7a3 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -2894,7 +2894,7 @@ vect_recog_divmod_pattern (vec *stmts, wide_int oprnd0_min, oprnd0_max; int msb = 1; - if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE) + if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max)) { if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype))) msb = 0; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 716a7c2..92abd00 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -498,6 +498,70 @@ abs_extent_range (value_range *vr, tree min, tree max) set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); } +/* Return TRUE if an irange is an ANTI_RANGE. This is a temporary + measure offering backward compatibility with range_info_def, and + will go away. */ + +static bool +irange_is_anti_range (irange r) +{ + const_tree type = r.get_type (); + // Remember: VR_ANTI_RANGE([3,10]) ==> [-MIN,2][11,MAX] + unsigned int precision = TYPE_PRECISION (type); + wide_int min = wi::min_value (precision, TYPE_SIGN (type)); + wide_int max = wi::max_value (precision, TYPE_SIGN (type)); + return (r.num_pairs () == 2 + && r.lower_bound () == min + && r.upper_bound () == max); +} + +/* Convert the range info of an SSA name into VRP's internal + value_range representation. Return VR_RANGE/VR_ANTI_RANGE if range + info is available for the SSA name, otherwise VR_VARYING is + returned. MIN/MAX is set if range info is available. + + FIXME: Any use of this function outside of tree-vrp must be + converted. For instnace, ipa-prop.c. */ + +enum value_range_type +get_range_info_as_value_range (const_tree ssa, wide_int *min, wide_int *max) +{ + if (!SSA_NAME_RANGE_INFO (ssa) + || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (ssa))) + > 2 * HOST_BITS_PER_WIDE_INT)) + return VR_VARYING; + + irange ri (ssa); + if (irange_is_anti_range (ri)) + { + irange tmp (ri); + tmp.invert (); + gcc_assert (!tmp.overflow_p ()); + if (tmp.num_pairs () != 1) + { + fprintf (stderr, "Inverse of anti range does not have 2 elements.\n"); + fprintf (stderr, "Type: "); + debug_generic_stmt (const_cast (ri.get_type ())); + fprintf (stderr, "Original anti range:\n"); + ri.dump (); + fprintf (stderr, "\n"); + fprintf (stderr, "Supposed inverse of anti range:\n"); + tmp.dump (); + fprintf (stderr, "\n"); + gcc_unreachable (); + } + *min = tmp.lower_bound (); + *max = tmp.upper_bound (); + return VR_ANTI_RANGE; + } + + /* We chop off any middle ranges, because range_info_def has no use + for such granularity. */ + *min = ri.lower_bound (); + *max = ri.upper_bound (); + return VR_RANGE; +} + /* Return value range information for VAR. @@ -555,7 +619,8 @@ get_value_range (const_tree var) else if (INTEGRAL_TYPE_P (TREE_TYPE (sym))) { wide_int min, max; - value_range_type rtype = get_range_info (var, &min, &max); + value_range_type rtype + = get_range_info_as_value_range (var, &min, &max); if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE) set_value_range (vr, rtype, wide_int_to_tree (TREE_TYPE (var), min), @@ -637,7 +702,7 @@ update_value_range (const_tree var, value_range *new_vr) if (INTEGRAL_TYPE_P (TREE_TYPE (var))) { wide_int min, max; - value_range_type rtype = get_range_info (var, &min, &max); + value_range_type rtype = get_range_info_as_value_range (var, &min, &max); if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE) { tree nr_min, nr_max; @@ -6887,9 +6952,10 @@ remove_range_assertions (void) && all_imm_uses_in_stmt_or_feed_cond (var, stmt, single_pred (bb))) { - set_range_info (var, SSA_NAME_RANGE_TYPE (lhs), - SSA_NAME_RANGE_INFO (lhs)->get_min (), - SSA_NAME_RANGE_INFO (lhs)->get_max ()); + wide_int min, max; + enum value_range_type rtype + = get_range_info_as_value_range (lhs, &min, &max); + set_range_info (var, rtype, min, max); maybe_set_nonzero_bits (bb, var); } } @@ -9903,7 +9969,7 @@ simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) case innerop was created during substitute-and-fold. */ wide_int imin, imax; if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)) - || get_range_info (innerop, &imin, &imax) != VR_RANGE) + || !get_range_info (innerop, &imin, &imax)) return false; innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop))); innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop))); diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index ef2c68a..99750cd 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -57,3 +57,5 @@ extern void extract_range_from_unary_expr (value_range *vr, value_range *vr0_, tree op0_type); +enum value_range_type get_range_info_as_value_range (const_tree ssa, + wide_int *min, wide_int *max); diff --git a/gcc/tree.c b/gcc/tree.c index db31620..a3b60d7 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -14277,7 +14277,6 @@ verify_type (const_tree t) } } - /* Return 1 if ARG interpreted as signed in its precision is known to be always positive or 2 if ARG is known to be always negative, or 3 if ARG may be positive or negative. */ @@ -14316,7 +14315,7 @@ get_range_pos_neg (tree arg) if (TREE_CODE (arg) != SSA_NAME) return 3; wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (!get_range_info (arg, &arg_min, &arg_max)) { gimple *g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) @@ -14326,6 +14325,8 @@ get_range_pos_neg (tree arg) if (INTEGRAL_TYPE_P (TREE_TYPE (t)) && TYPE_PRECISION (TREE_TYPE (t)) <= prec) { + /* Narrower value zero extended into wider type + will always result in positive values. */ if (TYPE_UNSIGNED (TREE_TYPE (t)) && TYPE_PRECISION (TREE_TYPE (t)) < prec) return 1; diff --git a/gcc/tree.h b/gcc/tree.h index c6e883c..8069302 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1740,14 +1740,6 @@ extern void protected_set_expr_location (tree, location_t); #define SSA_NAME_PTR_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.ptr_info -/* True if SSA_NAME_RANGE_INFO describes an anti-range. */ -#define SSA_NAME_ANTI_RANGE_P(N) \ - SSA_NAME_CHECK (N)->base.static_flag - -/* The type of range described by SSA_NAME_RANGE_INFO. */ -#define SSA_NAME_RANGE_TYPE(N) \ - (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE) - /* Value range info attributes for SSA_NAMEs of non pointer-type variables. */ #define SSA_NAME_RANGE_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.range_info diff --git a/gcc/wide-int.h b/gcc/wide-int.h index 2115b61..1d21f64 100644 --- a/gcc/wide-int.h +++ b/gcc/wide-int.h @@ -1341,6 +1341,7 @@ private: public: void set_precision (unsigned int); trailing_wide_int operator [] (unsigned int); + const trailing_wide_int operator [] (unsigned int) const; static size_t extra_size (unsigned int); }; @@ -1413,6 +1414,17 @@ trailing_wide_ints ::operator [] (unsigned int index) &m_val[index * m_max_len]); } +/* Return an RVAL to element INDEX. */ +template +inline const trailing_wide_int +trailing_wide_ints::operator [] (unsigned int index) const +{ + return trailing_wide_int_storage + (m_precision, + const_cast(&m_len[index]), + const_cast(&m_val[index * m_max_len])); +} + /* Return how many extra bytes need to be added to the end of the structure in order to handle N wide_ints of precision PRECISION. */ template