From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 105817 invoked by alias); 4 Sep 2018 14:12:38 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 102931 invoked by uid 89); 4 Sep 2018 14:12:37 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.8 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=HX-Received:sk:g4-v6mr X-HELO: mail-wr1-f42.google.com Received: from mail-wr1-f42.google.com (HELO mail-wr1-f42.google.com) (209.85.221.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 04 Sep 2018 14:12:34 +0000 Received: by mail-wr1-f42.google.com with SMTP id o37-v6so4138166wrf.6 for ; Tue, 04 Sep 2018 07:12:34 -0700 (PDT) Return-Path: Received: from abulafia.quesejoda.com (247.red-79-147-188.dynamicip.rima-tde.net. [79.147.188.247]) by smtp.gmail.com with ESMTPSA id o19-v6sm24223608wro.50.2018.09.04.07.12.30 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 04 Sep 2018 07:12:31 -0700 (PDT) Subject: Re: VRP: abstract out wide int CONVERT_EXPR_P code To: Richard Biener Cc: GCC Patches References: <30744ab3-510b-fc67-ad59-906fd54c50cf@redhat.com> From: Aldy Hernandez Message-ID: Date: Tue, 04 Sep 2018 14:12:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------E9E205A6EEFC9B54770BDA92" X-IsSubscribed: yes X-SW-Source: 2018-09/txt/msg00189.txt.bz2 This is a multi-part message in MIME format. --------------E9E205A6EEFC9B54770BDA92 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-length: 6146 On 09/04/2018 08:49 AM, Richard Biener wrote: > On Tue, Sep 4, 2018 at 2:41 PM Aldy Hernandez wrote: >> >> >> >> On 09/04/2018 07:58 AM, Richard Biener wrote: >>> On Mon, Sep 3, 2018 at 1:32 PM Aldy Hernandez wrote: >>>> >>>> >>>> >>>> On 08/28/2018 05:27 AM, Richard Biener wrote: >>>>> On Mon, Aug 27, 2018 at 2:24 PM Aldy Hernandez wrote: >>>>>> >>>>>> Howdy! >>>>>> >>>>>> Phew, I think this is the last abstraction. This handles the unary >>>>>> CONVERT_EXPR_P code. >>>>>> >>>>>> It's the usual story-- normalize the symbolics to [-MIN,+MAX] and handle >>>>>> everything generically. >>>>>> >>>>>> Normalizing the symbolics brought about some nice surprises. We now >>>>>> handle a few things we were punting on before, which I've documented in >>>>>> the patch, but can remove if so desired. I wrote them mainly for myself: >>>>>> >>>>>> /* NOTES: Previously we were returning VARYING for all symbolics, but >>>>>> we can do better by treating them as [-MIN, +MAX]. For >>>>>> example, converting [SYM, SYM] from INT to LONG UNSIGNED, >>>>>> we can return: ~[0x8000000, 0xffffffff7fffffff]. >>>>>> >>>>>> We were also failing to convert ~[0,0] from char* to unsigned, >>>>>> instead choosing to return VR_VARYING. Now we return ~[0,0]. */ >>>>>> >>>>>> Tested on x86-64 by the usual bootstrap and regtest gymnastics, >>>>>> including --enable-languages=all, because my past sins are still >>>>>> haunting me. >>>>>> >>>>>> OK? >>>>> >>>>> The new wide_int_range_convert_tree looks odd given it returns >>>>> tree's. I'd have expected an API that does the conversion resulting >>>>> in a wide_int range and the VRP code adapting to that by converting >>>>> the result to trees. >>>> >>>> Rewritten as suggested. >>>> >>>> A few notes. >>>> >>>> First. I am not using widest_int as was done previously. We were >>>> passing 0/false to the overflow args in force_fit_type so the call was >>>> just degrading into wide_int_to_tree() anyhow. Am I missing some >>>> subtlety here, and must we use widest_int and then force_fit_type on the >>>> caller? >>> >>> The issue is that the wide-ints get "converted", so it's indeed subtle. >> >> This seems like it should be documented-- at the very least in >> wide_int_range_convert. > > I don't think you need it there. > >> What do you mean "converted"? I'd like to understand this better before >> I write out the comment :). Do we lose precision by keeping it in a >> wide_int as opposed to a widest_int? > > As you're using wide_int::from that "changes" precision now. Ah, so it's wide_int_to_tree that wants to see the widest precision. I see. > >> Also, can we have the caller to wide_int_range_convert() use >> wide_int_to_tree directly instead of passing through force_fit_type? > > I think so. > >> It >> seems force_fit_type with overflowable=0 and overflowed=false is just a >> call to wide_int_to_tree anyhow. >> >>> >>> + || wi::rshift (wi::sub (vr0_max, vr0_min), >>> + wi::uhwi (outer_prec, inner_prec), >>> + inner_sign) == 0) >>> >>> this was previously allowed only for VR_RANGEs - now it's also for >>> VR_ANTI_RANGE. >>> That looks incorrect. Testcase welcome ;) >> >> See change to extract_range_into_wide_ints. VR_ANTI_RANGEs of constants >> will remain as is, whereas VR_ANTI_RANGEs of symbols will degrade into >> [-MIN,+MAX] and be handled generically. >> >> Also, see comment: >> >> + /* We normalize everything to a VR_RANGE, but for constant >> + anti-ranges we must handle them by leaving the final result >> + as an anti range. This allows us to convert things like >> + ~[0,5] seamlessly. */ > > Yes, but for truncation of ~[0, 5] from say int to short it's not correct > to make the result ~[0, 5], is it? At least the original code dropped > that to VARYING. For the same reason truncating [3, 765] from > short to unsigned char isn't [3, 253]. But maybe I'm missing something. Correct, but in that case we will realize that in wide_int_range_convert and refuse to do the conversion: /* If the conversion is not truncating we can convert the min and max values and canonicalize the resulting range. Otherwise we can do the conversion if the size of the range is less than what the precision of the target type can represent. */ if (outer_prec >= inner_prec || wi::rshift (wi::sub (vr0_max, vr0_min), wi::uhwi (outer_prec, inner_prec), inner_sign) == 0) > >>> >>> + return (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign)) >>> + || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign))); >>> >>> so you return false for VARYING? Why? I'd simply return true and >>> return VARYING in the new type in the path you return false. >> >> Since symbols and VR_VARYING and other things get turned into a >> [-MIN,+MAX] by extract_range_into_wide_ints, it's a lot easier to handle >> things generically and return varying when the range spans the entire >> domain. It also keeps with the rest of the wide_int_range_* functions >> that return false when we know it's going to be VR_VARYING. > > Ah, OK, didn't know they did that. Not sure if that's convenient though > given VR_VARYING has no representation in the wide-int-range "range" > so callers chaining ops would need to do sth like > > if (!wide_int_range_* (...., &out_min, &out_max)) > { > out_min = wide_int::min (prec); > out_max = wide_int::max (prec); > } > if (!wide_int_range_* (out_min, out_max, ....)) > ... > > to not lose cases where VARYING inputs produce non-VARYING results? Well in the ssa-range branch we treat [-MIN,+MAX] as varying. We call it range_for_type(). Also, the above if(!wide_int_range*) chaining is not necessary in the ssa-range work. See op_wi() in range-op.c. We just return false and the caller loop takes care of things. (Andrew's forte is not readable function names ;-). When I have my way with range-op.c, this op_RANDOM_TWO_LETTERS nonsense will go away.) OK for trunk? Aldy --------------E9E205A6EEFC9B54770BDA92 Content-Type: text/x-patch; name="curr.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="curr.patch" Content-length: 6809 gcc/ * wide-int-range.cc (wide_int_range_convert): New. * wide-int-range.h (wide_int_range_convert): New. * tree-vrp.c (extract_range_from_unary_expr): Abstract wide int code into wide_int_range_convert. (extract_range_into_wide_ints): Do not munge anti range constants into the entire domain. Just return the range back. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d29a2c9b507..2a3797e7f24 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -995,7 +995,7 @@ ranges_from_anti_range (const value_range *ar, /* Extract the components of a value range into a pair of wide ints in [WMIN, WMAX]. - If the value range is anything but a VR_RANGE of constants, the + If the value range is anything but a VR_*RANGE of constants, the resulting wide ints are set to [-MIN, +MAX] for the type. */ static void inline @@ -1003,7 +1003,10 @@ extract_range_into_wide_ints (const value_range *vr, signop sign, unsigned prec, wide_int &wmin, wide_int &wmax) { - if (range_int_cst_p (vr)) + if ((vr->type == VR_RANGE + || vr->type == VR_ANTI_RANGE) + && TREE_CODE (vr->min) == INTEGER_CST + && TREE_CODE (vr->max) == INTEGER_CST) { wmin = wi::to_wide (vr->min); wmax = wi::to_wide (vr->max); @@ -1850,44 +1853,42 @@ extract_range_from_unary_expr (value_range *vr, return; } - /* If VR0 is varying and we increase the type precision, assume - a full range for the following transformation. */ - if (vr0.type == VR_VARYING - && INTEGRAL_TYPE_P (inner_type) - && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)) - { - vr0.type = VR_RANGE; - vr0.min = TYPE_MIN_VALUE (inner_type); - vr0.max = TYPE_MAX_VALUE (inner_type); - } - - /* If VR0 is a constant range or anti-range and the conversion is - not truncating we can convert the min and max values and - canonicalize the resulting range. Otherwise we can do the - conversion if the size of the range is less than what the - precision of the target type can represent and the range is - not an anti-range. */ - if ((vr0.type == VR_RANGE - || vr0.type == VR_ANTI_RANGE) + /* We normalize everything to a VR_RANGE, but for constant + anti-ranges we must handle them by leaving the final result + as an anti range. This allows us to convert things like + ~[0,5] seamlessly. */ + value_range_type vr_type = VR_RANGE; + if (vr0.type == VR_ANTI_RANGE && TREE_CODE (vr0.min) == INTEGER_CST - && TREE_CODE (vr0.max) == INTEGER_CST - && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type) - || (vr0.type == VR_RANGE - && integer_zerop (int_const_binop (RSHIFT_EXPR, - int_const_binop (MINUS_EXPR, vr0.max, vr0.min), - size_int (TYPE_PRECISION (outer_type))))))) + && TREE_CODE (vr0.max) == INTEGER_CST) + vr_type = VR_ANTI_RANGE; + + /* NOTES: Previously we were returning VARYING for all symbolics, but + we can do better by treating them as [-MIN, +MAX]. For + example, converting [SYM, SYM] from INT to LONG UNSIGNED, + we can return: ~[0x8000000, 0xffffffff7fffffff]. + + We were also failing to convert ~[0,0] from char* to unsigned, + instead choosing to return VR_VARYING. Now we return ~[0,0]. */ + wide_int vr0_min, vr0_max; + widest_int wmin, wmax; + signop inner_sign = TYPE_SIGN (inner_type); + signop outer_sign = TYPE_SIGN (outer_type); + unsigned inner_prec = TYPE_PRECISION (inner_type); + unsigned outer_prec = TYPE_PRECISION (outer_type); + extract_range_into_wide_ints (&vr0, inner_sign, inner_prec, + vr0_min, vr0_max); + if (wide_int_range_convert (wmin, wmax, + inner_sign, inner_prec, + outer_sign, outer_prec, + vr0_min, vr0_max)) { - tree new_min, new_max; - new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), - 0, false); - new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), - 0, false); - set_and_canonicalize_value_range (vr, vr0.type, - new_min, new_max, NULL); - return; + tree min = wide_int_to_tree (outer_type, wmin); + tree max = wide_int_to_tree (outer_type, wmax); + set_and_canonicalize_value_range (vr, vr_type, min, max, NULL); } - - set_value_range_to_varying (vr); + else + set_value_range_to_varying (vr); return; } else if (code == ABS_EXPR) diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 04d391b33d5..aa25b88b982 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -735,6 +735,42 @@ wide_int_range_abs (wide_int &min, wide_int &max, return true; } +/* Convert range in [VR0_MIN, VR0_MAX] with INNER_SIGN and INNER_PREC, + to a widest_int range in [MIN, MAX] with OUTER_SIGN and OUTER_PREC. + + Return TRUE if we were able to successfully calculate the new range. + + Caller is responsible for canonicalizing the resulting range. */ + +bool +wide_int_range_convert (widest_int &min, widest_int &max, + signop inner_sign, + unsigned inner_prec, + signop outer_sign, + unsigned outer_prec, + const wide_int &vr0_min, + const wide_int &vr0_max) +{ + /* If the conversion is not truncating we can convert the min and + max values and canonicalize the resulting range. Otherwise we + can do the conversion if the size of the range is less than what + the precision of the target type can represent. */ + if (outer_prec >= inner_prec + || wi::rshift (wi::sub (vr0_max, vr0_min), + wi::uhwi (outer_prec, inner_prec), + inner_sign) == 0) + { + min = widest_int::from (vr0_min, inner_sign); + max = widest_int::from (vr0_max, inner_sign); + widest_int min_value + = widest_int::from (wi::min_value (outer_prec, outer_sign), outer_sign); + widest_int max_value + = widest_int::from (wi::max_value (outer_prec, outer_sign), outer_sign); + return !wi::eq_p (min, min_value) || !wi::eq_p (max, max_value); + } + return false; +} + /* Calculate a division operation on two ranges and store the result in [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX]. diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index eaf47bca449..d0efd5ca694 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -109,6 +109,13 @@ extern bool wide_int_range_abs (wide_int &min, wide_int &max, const wide_int &vr0_min, const wide_int &vr0_max, bool overflow_undefined); +extern bool wide_int_range_convert (widest_int &min, widest_int &max, + signop inner_sign, + unsigned inner_prec, + signop outer_sign, + unsigned outer_prec, + const wide_int &vr0_min, + const wide_int &vr0_max); extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax, enum tree_code code, signop sign, unsigned prec, --------------E9E205A6EEFC9B54770BDA92--