From patchwork Tue May 23 10:48:15 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 765850 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wXC2P2NHHz9sP3 for ; Tue, 23 May 2017 20:49:17 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="UTce+qBU"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=rvz01SDhfIrfXGTsCE9OJTaCTGLUVvFaVL+cmBcXx0H7SQDy9c qsuAVb/YoI3fHyPUhIxA8/sEQssPuwBzMw4tpSW6gfFR/Xw6X7oaKvFLl+AFG6Vd DyykanFfL+nj2av7TAV34u5BDETao4X17XwAr0M61koAsqb91mJuK9VdA= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:message-id:date:mime-version:content-type; s= default; bh=GPLD+UFDPq37Zv746Xy8CXeybTw=; b=UTce+qBU2zMi9Q0/xWbe NENAM26UIEISoWX/zLtvZlgF1Phncbwxt0y35+T0uoEf9xCRVLWtxafciSxh+/JE KBjurL1KLXv00RNC8oCegW0kjUMU2mIedgANaiOyNnTrCu/KPP7VdDEVF0rlaCZF VeHfWPAls1/j+cpXnrqBtGY= Received: (qmail 103925 invoked by alias); 23 May 2017 10:48:55 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 103727 invoked by uid 89); 23 May 2017 10:48:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=maxlen, x, y, Supposed X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 23 May 2017 10:48:29 +0000 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id E79BB17AC58; Tue, 23 May 2017 10:48:19 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com E79BB17AC58 Authentication-Results: ext-mx10.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx10.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=aldyh@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com E79BB17AC58 Received: from abulafia.quesejoda.com (ovpn-117-83.ams2.redhat.com [10.36.117.83]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4CC687EA54; Tue, 23 May 2017 10:48:15 +0000 (UTC) To: Richard Biener Cc: Andrew MacLeod , gcc-patches From: Aldy Hernandez Subject: SSA range class and removal of VR_ANTI_RANGEs Message-ID: Date: Tue, 23 May 2017 06:48:15 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.0 MIME-Version: 1.0 Howdy! For Andrew's upcoming on-demand range work I have created a range class for use in his engine. Currently, the range class is only for SSA integers, but there is no reason why we couldn't adapt this for RTL or non-integer types at a later time. The class can live outside of his work, as can be demonstrated by the attached patch. With it, I was able to rewrite the post-VRP range information to use this class and get rid of VR_ANTI_RANGE throughout the compiler. A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX]. The internal structure of VRP is unchanged. I have only changed the outward facing structures. A good example of how much cleaner using an actual range rather than VR_ANTI_RANGEs is the change to get_size_range() in the attached patch. We remove an assortment of contortions into: + /* Remove negative numbers from the range. */ + irange positives; + range_positives (&positives, exptype, allow_zero ? 0 : 1); + if (positives.Intersect (*ir)) + { + /* Remove the unknown parts of a multi-range. + This will transform [5,10][20,MAX] into [5,10]. */ + if (positives.num_ranges () > 1 + && positives.upper_bound () == wide_int (TYPE_MAX_VALUE (exptype))) + positives.remove_range (positives.num_ranges () - 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); } A few notes: 1. There are still two uses of VR_ANTI_RANGEs left after this patch: ip-cp.c and ipa-prop.c. I didn't look too hard at these two passes, as they are using `struct value_range' which should only have been used *before* VRP finishes. I can work on this as a follow-up. 2. I have not included ChangeLog entries, as I would hate to write them, and have the API or significant things change from under me as part of the review. I can certainly cobble the ChangeLog entries as soon as/if we agree that this is an acceptable approach. 3. There are lots of unit tests to maintain sanity. The cast ones in particular will definitely need refinement as Andrew's work stresses the class. The attached patch passes bootstrap and tests. I have also benchmarked an assortment of .ii files (from a previous bootstrap) with no noticeable difference in -O2 compilation time. So, I would prefer to tackle any micro-optimizations either as a follow-up or if it actually becomes noticeable--. Yeah, yeah, I know. Wishful thinking ;-). Fire away! Aldy p.s. Please refer any comments as to why we need the class, or why we need on-demand range information to Andrew :-P. 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..328f028 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_ranges () != 2 + || ir.lower_bound () != 0) + return false; + + 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) + if (range_may_have_wrapped (*SSA_NAME_RANGE_INFO (len), + 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, /*allow_zero=*/true); /* 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..3070878 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. + + INCLUDE_ZERO is TRUE if 0 should be included in a valid range. */ bool -get_size_range (tree exp, tree range[2]) +get_size_range (tree exp, tree range[2], bool allow_zero) { if (tree_fits_uhwi_p (exp)) { @@ -1269,11 +1272,10 @@ get_size_range (tree exp, tree range[2]) } wide_int min, max; - enum value_range_type range_type + irange *ir = ((TREE_CODE (exp) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (exp))) - ? get_range_info (exp, &min, &max) : VR_VARYING); - - if (range_type == VR_VARYING) + ? get_range_info (exp, &min, &max) : NULL); + if (!ir) { /* No range information available. */ range[0] = NULL_TREE; @@ -1282,61 +1284,29 @@ get_size_range (tree exp, tree range[2]) } 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, allow_zero ? 0 : 1); + if (positives.Intersect (*ir)) { - 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_ranges () > 1 + && positives.upper_bound () == wide_int (TYPE_MAX_VALUE (exptype))) + positives.remove_range (positives.num_ranges () - 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..85ad78c 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], bool include_zero = false); #endif // GCC_CALLS_H diff --git a/gcc/fold-const.c b/gcc/fold-const.c index 736552c..0c48018 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,7 @@ bool expr_not_equal_to (tree t, const wide_int &w) { wide_int min, max, nz; - value_range_type rtype; + irange *ri; switch (TREE_CODE (t)) { case INTEGER_CST: @@ -9072,17 +9073,8 @@ 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 (wi::lt_p (max, w, TYPE_SIGN (TREE_TYPE (t)))) - return true; - if (wi::lt_p (w, min, TYPE_SIGN (TREE_TYPE (t)))) - 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)))) + ri = SSA_NAME_RANGE_INFO (t); + if (ri && !ri->contains_p (w)) 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. */ 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.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..9ae5453 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)) + irange *ri = SSA_NAME_RANGE_INFO (node); + if (!POINTER_TYPE_P (TREE_TYPE (node)) && ri) { - wide_int min, max, nonzero_bits; - value_range_type range_type = get_range_info (node, &min, &max); + 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..9f96af4 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 = SSA_NAME_RANGE_INFO (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-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..2506185 --- /dev/null +++ b/gcc/range.c @@ -0,0 +1,1317 @@ +/* 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" + + +void +irange::set_range (tree t, wide_int lbound, wide_int ubound, + irange_type rt) +{ + gcc_assert (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t)); + gcc_assert (TYPE_PRECISION (t) == lbound.get_precision ()); + gcc_assert (lbound.get_precision () == ubound.get_precision ()); + overflow = false; + type = t; + gcc_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type))); + if (rt == RANGE_INVERT) + { + // We calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. + bool ovf; + n = 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[n++] = min; + bounds[n++] = wi::sub (lbound, 1, TYPE_SIGN (type), &ovf); + if (ovf) + n = 0; + } + // If we will overflow, don't bother. This will handle unsigned + // overflow which doesn't set the overflow bit. + if (ubound != max) + { + bounds[n++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf); + if (ovf) + n--; + else + bounds[n++] = 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 + { + n = 2; + bounds[0] = lbound; + bounds[1] = ubound; + } +} + +void +irange::set_range (tree type) +{ + gcc_assert (TYPE_P (type)); + gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)); + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + set_range (type, min, max); +} + +irange::irange (tree t, wide_int lbound, wide_int ubound, + irange_type rt) +{ + set_range (t, lbound, ubound, rt); +} + +irange::irange (const irange &r) +{ + type = r.type; + overflow = false; + n = r.n; + for (unsigned i = 0; i < n; ++i) + bounds[i] = r.bounds[i]; +} + +// Build a range for the entire domain for TYPE. + +irange::irange (tree type) +{ + gcc_assert (TYPE_P (type)); + set_range (type); +} + +bool +irange::operator== (const irange &r) const +{ + if (type != r.type || n != r.n || overflow != r.overflow) + return false; + for (unsigned i = 0; i < n; ++i) + if (bounds[i] != r.bounds[i]) + return false; + return true; +} + +irange& +irange::operator= (const irange &r) +{ + type = r.type; + n = r.n; + overflow = r.overflow; + for (unsigned i = 0; i < n; ++i) + bounds[i] = r.bounds[i]; + return *this; +} + + +irange& +irange::operator= (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 (type); + return (*this == tmp); +} + + +bool +irange::valid_p () +{ + if (!n) + return false; + if (n % 2) + return false; + if (n > MAX_RANGES) + 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 < n; 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 (tree new_type) +{ + if (!n) + { + 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)) + { + // Get the extreme bounds for the new type, but within the old type, + // so we can properly compare them. + wide_int lbound = fold_convert (type, TYPE_MIN_VALUE (new_type)); + wide_int ubound = fold_convert (type, TYPE_MAX_VALUE (new_type)); + + if (wi::lt_p (bounds[0], lbound, TYPE_SIGN (type)) + || wi::gt_p (bounds[n - 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; + n = 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 < n; i += 2) + { + tree b0 = fold_convert (new_type, wide_int_to_tree (type, bounds[i])); + tree b1 = fold_convert (new_type, wide_int_to_tree (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 (n >= MAX_RANGES) + { + bounds[0] = orig_low; + bounds[1] = orig_high; + n = 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; + n = 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[n++] = b0; + bounds[n++] = max; + } + // From sign bit to no sign bit: [-5, 5] => [251,255][0,5] + else + { + bounds[i] = min; + bounds[i + 1] = b1; + bounds[n++] = b0; + bounds[n++] = max; + } + } + } + type = new_type; + if (sign_change) + canonicalize (); + gcc_assert (valid_p ()); +} + +// Return TRUE if the current range contains ELEMENT. + +bool +irange::contains_p (wide_int element) +{ + for (unsigned i = 0; i < n; 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 (tree element) +{ + gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (element))); + element = fold_convert (type, element); + if (TREE_OVERFLOW (element)) + return false; + wide_int wi = element; + return contains_p (wi); +} + +// Canonicalize the current range. + +void +irange::canonicalize () +{ + if (n < 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 < n - 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 < n - 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 (wide_int x, wide_int y) +{ + // If we have enough space, shift everything to the right and prepend. + if (n < MAX_RANGES) + { + for (unsigned i = n; i; i -= 2) + { + bounds[i] = bounds[i - 2]; + bounds[i + 1] = bounds[i - 1]; + } + bounds[0] = x; + bounds[1] = y; + n += 2; + } + // Otherwise, merge it with the first entry. + else + bounds[0] = x; + canonicalize (); +} + +// Place [X,Y] at the end of THIS. + +void +irange::append (wide_int x, wide_int y) +{ + // If we have enough space, make space at the end and append. + if (n < MAX_RANGES) + { + bounds[n++] = x; + bounds[n++] = y; + } + // Otherwise, merge it with the last entry. + else + bounds[n - 1] = y; + canonicalize (); +} + +// Remove the bound entries from [i..j]. + +void +irange::remove (unsigned i, unsigned j) +{ + gcc_assert (i < n && i < j); + unsigned dst = i; + unsigned ndeleted = j - i + 1; + for (++j; j < n; ++j) + bounds[dst++] = bounds[j]; + n -= ndeleted; +} + +// THIS = THIS U [X,Y] + +void +irange::Union (wide_int x, wide_int y) +{ + if (empty_p ()) + { + bounds[0] = x; + bounds[1] = y; + n = 2; + return; + } + + // If [X,Y] comes before, put it at the front. + if (wi::lt_p (y, bounds[0], TYPE_SIGN (type))) + { + prepend (x, y); + return; + } + // If [X,Y] comes after, put it at the end. + if (wi::gt_p (x, bounds[n - 1], TYPE_SIGN (type))) + { + append (x, y); + return; + } + // Handle [X,Y] swalling up all of THIS. + if (wi::le_p (x, bounds[0], TYPE_SIGN (type)) + && wi::ge_p (y, bounds[n - 1], TYPE_SIGN (type))) + { + bounds[0] = x; + bounds[1] = y; + n = 2; + return; + } + // 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 (n == 2) + return; + + for (unsigned i = 1; i < n; 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; + } + 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[n - 1], TYPE_SIGN (type))) + { + for (unsigned i = 0; i < n; i += 2) + if (wi::ge_p (bounds[i + 1], x, TYPE_SIGN (type))) + { + bounds[i + 1] = y; + n = i + 2; + return; + } + 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[n - 1], TYPE_SIGN (type))); + + // Find X. + gcc_assert (n >= 2); + unsigned xpos = ~0U; + unsigned i = n; + 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 < n; 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; + + // Merge the sub-ranges in between xpos and ypos. + y = bounds[ypos]; + remove (xpos + 2, ypos); + bounds[xpos + 1] = y; +} + +// THIS = R1 U R2 + +bool +irange::Union (const irange &r1, const irange &r2) +{ + gcc_assert (r1.type == r2.type); + + if (r1.empty_p ()) + { + *this = r2; + return true; + } + else if (r2.empty_p ()) + { + *this = r1; + return true; + } + + *this = r1; + for (unsigned i = 0; i < r2.n; i += 2) + Union (r2.bounds[i], r2.bounds[i + 1]); + + overflow |= r1.overflow; + return true; +} + +// THIS = THIS U R + +bool +irange::Union (const irange &r) +{ + if (*this == r) + return true; + return Union (*this, r); +} + +// THIS = THIS ^ [X,Y] +// +// Returns TRUE if the result of the intersection is non-empty. +// +// If READONLY is TRUE, we are only interested in determining if the +// operation will yield a non-empty value. THIS is left unchanged. + +bool +irange::Intersect (wide_int x, wide_int y, bool readonly) +{ + unsigned pos = 0; + + for (unsigned i = 0; i < n; 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 + { + if (readonly) + return true; + bounds[pos++] = newlo; + bounds[pos++] = newhi; + } + } + n = pos; + return n != 0; +} + +// THIS = R1 ^ R2 +// +// Returns TRUE if the result of the intersection is non-empty. +// +// If READONLY is TRUE, we are only interested in determining if the +// operation will yield a non-empty value. THIS is left unchanged. + +bool +irange::Intersect (const irange &r1, const irange &r2, bool readonly) +{ + gcc_assert (r1.type == r2.type); + + if (!readonly) + clear (r1.type); + + // Intersection with an empty range is an empty range. + if (r1.empty_p () || r2.empty_p ()) + return false; + + // The general algorithm is as follows. + // + // Intersect each sub-range of R2 with all of R1 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 accumulate into a new range instead of + // joining at each step, and stop making a copy of R1 at every step. + + for (unsigned i = 0; i < r2.n; i += 2) + { + irange chunk (r1); + if (chunk.Intersect (r2.bounds[i], r2.bounds[i + 1])) + { + if (readonly) + return true; + Union (chunk); + } + } + + // Overflow is sticky only if both ranges overflowed. + overflow = (r1.overflow && r2.overflow); + return n != 0; +} + +// THIS = THIS ^ R +// +// Returns TRUE if the result of the intersection is non-empty. +// +// If READONLY is TRUE, we are only interested in determining if the +// operation will yield a non-empty value. THIS is left unchanged. + +bool +irange::Intersect (const irange &r, bool readonly) +{ + irange q = *this; + return Intersect (q, r, readonly); +} + +// THIS = NOT(R). + +bool +irange::Not (const irange& r) +{ + type = r.type; + overflow = r.overflow; + + // We always need one more set of bounds to represent a NOT, so if + // we're at the limit, we can't properly represent things. + // + // For instance, to represent a NOT 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 NOT of that. + if (r.n >= MAX_RANGES) + { + bounds[0] = r.bounds[0]; + bounds[1] = r.bounds[n - 1]; + n = 2; + return Not (); + } + + // The inverse of the empty set is the entire domain. + if (r.empty_p ()) + { + set_range (type); + return false; + } + + // The algorithm is as follows. To calculate NOT ([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 NOT([-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. + n = 0; + wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + // 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 != r.bounds[i]) + { + bounds[n++] = min; + bounds[n++] = wi::sub (r.bounds[i], 1, TYPE_SIGN (type), &ovf); + if (ovf) + n = 0; + } + i++; + // Construct middle ranges if applicable. + if (r.n > 2) + { + unsigned j = i; + for (; j < r.n - 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[n++] = wi::add (r.bounds[j], 1, TYPE_SIGN (type), &ovf); + bounds[n++] = wi::sub (r.bounds[j + 1], 1, TYPE_SIGN (type), &ovf); + if (ovf) + n -= 2; + } + i = j; + } + // Construct rightmost range. + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + // 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 != r.bounds[i]) + { + bounds[n++] = wi::add (r.bounds[i], 1, TYPE_SIGN (type), &ovf); + bounds[n++] = max; + if (ovf) + n -= 2; + } + + return n != 0; +} + +// THIS = Not (THIS). + +bool +irange::Not () +{ + irange tmp (*this); + return Not (tmp); +} + +wide_int +irange::lower_bound (unsigned index) +{ + gcc_assert (n != 0 && index <= n/2); + return bounds[index * 2]; +} + +wide_int +irange::upper_bound (unsigned index) +{ + gcc_assert (n != 0 && index <= n/2); + return bounds[index * 2 + 1]; +} + +/* Dump the current range onto BUFFER. */ + +void +irange::dump (pretty_printer *buffer) +{ + if (!n) + { + pp_string (buffer, "[]"); + return; + } + for (unsigned i = 0; i < n; ++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); +} + +bool +make_irange (irange_p result, tree lb, tree ub, 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_p result, tree not_exp, tree type) +{ + irange r (TREE_TYPE (not_exp), not_exp, not_exp, RANGE_INVERT); + *result = r; + if (result->valid_p ()) + { + if (type) + result->cast (type); + return true; + } + return false; +} + +void +range_one (irange_p r, tree type) +{ + tree one = build_int_cst (type, 1); + r->set_range (type, one, one); +} + +void +range_zero (irange_p r, tree type) +{ + tree zero = build_int_cst (type, 0); + r->set_range (type, zero, zero); +} + +bool +range_non_zero (irange_p 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_p 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), RANGE_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.Not (); + ASSERT_TRUE (r0 == r1); + + r0.set_range (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 (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 (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), RANGE_PLAIN); + r0.Not (); + 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, RANGE_PLAIN); + r0.Not (); + 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), RANGE_INVERT); + 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), RANGE_INVERT); + 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_RANGES 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 (MAX_RANGES * 10 + 10 < 32767); + for (unsigned i = 2; i < MAX_RANGES; 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(50)); + 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))); + ASSERT_TRUE (r1.Not ()); + ASSERT_TRUE (r1 == r2); + // Test that NOT(NOT(x)) == x. + ASSERT_TRUE (r2.Not ()); + 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_FALSE (r0.Not ()); + r1.clear (); + ASSERT_TRUE (r0 == r1); + + // Test uninitialized.Not(xxx). + r0 = RANGE1 (10, 20); + { + irange uninitialized; + uninitialized.Not(r0); + r1 = irange (integer_type_node, INT(10), INT(20), RANGE_INVERT); + ASSERT_TRUE (uninitialized == 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.Not(); + 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); + + // ([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)); + // [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.Not(); + r0.Not (); + ASSERT_TRUE (r0 == r1); + + // [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)); + + 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)); + + // [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)); + + // [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)); + + // [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][30,40] U [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 (r0.Intersect_p (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..2a2ea06 --- /dev/null +++ b/gcc/range.h @@ -0,0 +1,111 @@ +/* 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 +#define MAX_RANGES 6 + +typedef class irange *irange_p; +enum irange_type { RANGE_PLAIN, RANGE_INVERT }; + +class GTY(()) irange +{ + private: + bool overflow; + size_t n; + void prepend (wide_int x, wide_int y); + void append (wide_int x, wide_int y); + void remove (unsigned i, unsigned j); + void canonicalize (); + /* This is stupid. These two should be private, but the GTY + machinery can't look inside an irange. */ + public: + tree type; + wide_int bounds[MAX_RANGES]; + +public: + irange () { type = NULL_TREE; n = 0; } + irange (tree t); + irange (tree t, wide_int lbound, wide_int ubound, + irange_type rt = RANGE_PLAIN); + irange (const irange &r); + + void set_range (tree t); + void set_range (tree t, wide_int lbound, wide_int ubound, + irange_type rt = RANGE_PLAIN); + + bool overflow_p () { return overflow && !TYPE_OVERFLOW_WRAPS (type); } + void set_overflow () { overflow = true; } + void clear_overflow () { overflow = false; } + + unsigned num_ranges () { return n / 2; } + wide_int lower_bound () const { return bounds[0]; } + wide_int lower_bound (unsigned index); + wide_int upper_bound () const { return bounds[n - 1]; } + wide_int upper_bound (unsigned index); + + void remove_range (unsigned i) { remove (i, i + 1); } + void clear () { n = 0; } + void clear (tree t) { type = t; n = 0; overflow = false; } + bool empty_p () const { return !n; } + bool range_for_type_p () const; + bool simple_range_p () const { return n == 2; } + + void dump (); + void dump (pretty_printer *pp); + void dump (FILE *); + + bool valid_p (); + void cast (tree type); + bool contains_p (wide_int element); + bool contains_p (tree); + + tree get_type () { return type; } + + irange& operator= (const irange &r); + irange& operator= (tree t); + + bool operator== (const irange &r) const; + bool operator!= (const irange &r) const { return !(*this == r); } + + void Union (wide_int x, wide_int y); + bool Union (const irange &r); + bool Union (const irange &r1, const irange &r2); + + // THIS = THIS ^ [X,Y]. Return TRUE if result is non-empty. + bool Intersect (wide_int x, wide_int y, bool readonly = false); + // THIS = THIS ^ R. Return TRUE if result is non-empty. + bool Intersect (const irange &r, bool readonly = false); + // THIS = R1 ^ R2. Return TRUE if result is non-empty. + bool Intersect (const irange &r1, const irange &r2, bool readonly = false); + // Return TRUE if THIS ^ R will be non-empty. + bool Intersect_p (const irange &r) + { return Intersect (r, /*readonly=*/true); } + + bool Not (); + bool Not (const irange& r); +}; + +void range_zero (irange_p r, tree type); +void range_one (irange_p r, tree type); +bool range_non_zero (irange_p r, tree type); +void range_positives (irange_p r, tree type, unsigned int); + +#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..139e328 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; 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 @@ -1416,11 +1413,15 @@ 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 *range_info; } GTY ((desc ("%1.typed.type ?" \ "!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info; + /* For non-pointer types, this specifies a mask for the bits that + are known to be set. */ + struct nonzero_bits_def *nonzero_bits; + /* Immediate uses list for this SSA_NAME. */ struct ssa_use_operand_t imm_uses; }; 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..7c02148 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), + SSA_NAME_NONZERO_BITS (var)); } } diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index c0e06bb..d7fb66f 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -1182,6 +1182,7 @@ move_computations_worker (basic_block bb) { tree lhs = gimple_assign_lhs (new_stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; + SSA_NAME_NONZERO_BITS (lhs) = NULL; } gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); remove_phi_node (&bsi, false); @@ -1251,6 +1252,7 @@ move_computations_worker (basic_block bb) { tree lhs = gimple_get_lhs (stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; + SSA_NAME_NONZERO_BITS (lhs) = NULL; } /* In case this is a stmt that is not unconditionally executed when the target loop header is executed and the stmt may diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index e67cd93..338efc4 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) != NULL; /* 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..43385a7 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -1063,13 +1063,14 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, : # u_3 = PHI */ SSA_NAME_RANGE_INFO (lhs) = NULL; + SSA_NAME_NONZERO_BITS (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 - = SSA_NAME_RANGE_INFO (phires); - if (phires_range_info) - duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires), - phires_range_info); + if (irange *phires_range_info = SSA_NAME_RANGE_INFO (phires)) + { + struct nonzero_bits_def *nzb = SSA_NAME_NONZERO_BITS (phires); + duplicate_ssa_name_range_info (lhs, phires_range_info, nzb); + } } 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..5e16dfc 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), + VN_INFO_NONZERO_BITS (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..7e94172 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -3351,12 +3351,11 @@ set_ssa_val_to (tree from, tree to) 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)->nonzero_bits = SSA_NAME_NONZERO_BITS (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); + SSA_NAME_NONZERO_BITS (to) = SSA_NAME_NONZERO_BITS (from); } else { @@ -3364,12 +3363,12 @@ set_ssa_val_to (tree from, tree to) 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)->nonzero_bits = SSA_NAME_NONZERO_BITS (to); } /* Rather than allocating memory and unioning the info just clear it. */ SSA_NAME_RANGE_INFO (to) = NULL; + SSA_NAME_NONZERO_BITS (to) = NULL; } } else if (POINTER_TYPE_P (TREE_TYPE (to)) @@ -4618,8 +4617,7 @@ scc_vn_restore_ssa_info (void) && 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_NONZERO_BITS (name) = VN_INFO (name)->nonzero_bits; } } } diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h index 77d0183..4b1557d 100644 --- a/gcc/tree-ssa-sccvn.h +++ b/gcc/tree-ssa-sccvn.h @@ -182,6 +182,9 @@ typedef struct vn_ssa_aux /* Saved SSA name info. */ tree_ssa_name::ssa_name_info_type info; + /* Saved SSA name nonzero bits info. */ + struct nonzero_bits_def *nonzero_bits; + /* Unique identifier that all expressions with the same value have. */ unsigned int value_id; @@ -201,9 +204,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 +262,7 @@ vn_valueize (tree name) /* Get at the original range info for NAME. */ -inline range_info_def * +inline irange * VN_INFO_RANGE_INFO (tree name) { return (VN_INFO (name)->info.range_info @@ -270,22 +270,14 @@ 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. */ +/* Get at the original nonzero bits info for NAME. */ -inline value_range_type -VN_INFO_RANGE_TYPE (tree name) +inline struct nonzero_bits_def * +VN_INFO_NONZERO_BITS (tree name) { - return VN_INFO_ANTI_RANGE_P (name) ? VR_ANTI_RANGE : VR_RANGE; + return (VN_INFO (name)->nonzero_bits + ? VN_INFO (name)->nonzero_bits + : SSA_NAME_NONZERO_BITS (name)); } /* Get at the original pointer info for NAME. */ diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 353c7b1..fd016d0 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -307,7 +307,10 @@ make_ssa_name_fn (struct function *fn, tree var, gimple *stmt, if (POINTER_TYPE_P (TREE_TYPE (t))) SSA_NAME_PTR_INFO (t) = NULL; else - SSA_NAME_RANGE_INFO (t) = NULL; + { + SSA_NAME_RANGE_INFO (t) = NULL; + SSA_NAME_NONZERO_BITS (t) = NULL; + } SSA_NAME_IN_FREE_LIST (t) = 0; SSA_NAME_IS_DEFAULT_DEF (t) = 0; @@ -328,59 +331,66 @@ 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 *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 = static_cast (ggc_internal_alloc (sizeof (irange))); SSA_NAME_RANGE_INFO (name) = ri; - ri->set_nonzero_bits (wi::shwi (-1, precision)); + + size_t size = (sizeof (nonzero_bits_def) + + trailing_wide_ints <1>::extra_size (precision)); + SSA_NAME_NONZERO_BITS (name) + = static_cast (ggc_internal_alloc (size)); + SSA_NAME_NONZERO_BITS (name)->ints.set_precision (precision); + SSA_NAME_NONZERO_BITS (name)->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); + gcc_assert (SSA_NAME_NONZERO_BITS (name) != NULL); - /* Set the values. */ - ri->set_min (min); - ri->set_max (max); + signop sign = TYPE_SIGN (TREE_TYPE (name)); + ri->set_range (TREE_TYPE (name), + wide_int::from (min, precision, sign), + wide_int::from (max, precision, sign), + range_type == VR_ANTI_RANGE ? RANGE_INVERT : RANGE_PLAIN); /* 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)); + wide_int nzb = SSA_NAME_NONZERO_BITS (name)->get_nonzero_bits (); + SSA_NAME_NONZERO_BITS (name)->set_nonzero_bits (nzb & (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 the range and sets MIN, MAX accordingly. If no range + information is available, returns NULL and MIN, MAX is + untouched. */ -enum value_range_type +irange * 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); + irange *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. */ + // FIXME: ?? Do we need this precision stuff ?? if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) > 2 * HOST_BITS_PER_WIDE_INT)) - return VR_VARYING; + return NULL; - *min = ri->get_min (); - *max = ri->get_max (); - return SSA_NAME_RANGE_TYPE (name); + gcc_assert (ri->valid_p ()); + *min = ri->lower_bound (); + *max = ri->upper_bound (); + return ri; } /* Set nonnull attribute to pointer NAME. */ @@ -422,8 +432,7 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) 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); - ri->set_nonzero_bits (mask); + SSA_NAME_NONZERO_BITS (name)->set_nonzero_bits (mask); } /* Return a widest_int with potentially non-zero bits in SSA_NAME @@ -442,11 +451,14 @@ get_nonzero_bits (const_tree name) return wi::shwi (-1, precision); } - range_info_def *ri = SSA_NAME_RANGE_INFO (name); + irange *ri = SSA_NAME_RANGE_INFO (name); if (!ri) - return wi::shwi (-1, precision); + { + gcc_assert (!SSA_NAME_NONZERO_BITS (name)); + return wi::shwi (-1, precision); + } - return ri->get_nonzero_bits (); + return SSA_NAME_NONZERO_BITS (name)->get_nonzero_bits (); } /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false @@ -676,28 +688,44 @@ 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 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 *range_info, + struct nonzero_bits_def *nonzero_bits) { - struct range_info_def *new_range_info; - gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (!SSA_NAME_RANGE_INFO (name)); + gcc_assert (!SSA_NAME_NONZERO_BITS (name)); if (!range_info) return; + /* Copy the non-zero bits information over. */ 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); + size_t size = (sizeof (nonzero_bits_def) + + trailing_wide_ints <1>::extra_size (precision)); + struct nonzero_bits_def *nzb + = static_cast (ggc_internal_alloc (size)); + memcpy (nzb, nonzero_bits, size); + SSA_NAME_NONZERO_BITS (name) = nzb; + + /* Copy the range info over. */ + size = sizeof (irange); + irange *new_range_info = static_cast (ggc_internal_alloc (size)); + *new_range_info = *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) != range_info->get_type ()) + range_info->cast (TREE_TYPE (name)); - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); SSA_NAME_RANGE_INFO (name) = new_range_info; } @@ -719,11 +747,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 *old_range_info = SSA_NAME_RANGE_INFO (name); + struct nonzero_bits_def *old_nzb = SSA_NAME_NONZERO_BITS (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, old_nzb); } return new_name; @@ -743,7 +771,10 @@ reset_flow_sensitive_info (tree name) mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name)); } else - SSA_NAME_RANGE_INFO (name) = NULL; + { + SSA_NAME_RANGE_INFO (name) = NULL; + SSA_NAME_NONZERO_BITS (name) = NULL; + } } /* Clear all flow sensitive data from all statements and PHI definitions diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index 9a18394..cdab953 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,8 +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 irange *get_range_info (const_tree, wide_int *, + wide_int *); extern void set_nonzero_bits (tree, const wide_int_ref &); extern wide_int get_nonzero_bits (const_tree); extern bool ssa_name_has_boolean_range (tree); @@ -95,8 +93,8 @@ 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 *, + struct nonzero_bits_def *); 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..b187446 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -498,6 +498,69 @@ 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) +{ + 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_ranges () == 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) +{ + irange *ri = SSA_NAME_RANGE_INFO (ssa); + if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (ssa))) + > 2 * HOST_BITS_PER_WIDE_INT)) + return VR_VARYING; + + if (irange_is_anti_range (*ri)) + { + irange tmp (*ri); + tmp.Not (); + gcc_assert (!tmp.overflow_p ()); + if (tmp.num_ranges () != 1) + { + fprintf (stderr, "Inverse of anti range does not have 2 elements.\n"); + fprintf (stderr, "Type: "); + debug_generic_stmt (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 +618,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 +701,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 +6951,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 +9968,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..cd4ae68 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -14316,7 +14316,10 @@ 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) + irange *ir; + while (!(ir = get_range_info (arg, &arg_min, &arg_max)) + || (ir->lower_bound () == TYPE_MIN_VALUE (TREE_TYPE (arg)) + && ir->upper_bound () == TYPE_MAX_VALUE (TREE_TYPE (arg)))) { gimple *g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) @@ -14326,6 +14329,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..1878f41 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1740,18 +1740,19 @@ 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 +/* Known used bits for a non pointer-type variable. + + Actual wide_int value is accessed with: + SSA_NAME_NONZERO_BITS(x)->get_nonzero_bits() + and set with: + SSA_NAME_NONZERO_BITS(x)->set_nonzero_bits(). */ +#define SSA_NAME_NONZERO_BITS(N) \ + SSA_NAME_CHECK (N)->ssa_name.nonzero_bits + /* Return the immediate_use information for an SSA_NAME. */ #define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses